9
$\begingroup$

What is the ratio of ambiguous CFGs to all CFGs?

Since both sets are countably infinite the ratio is not well-defined. But what about the asymptotic density:

$$\lim_{n \mapsto \infty}\frac {\# \text{ ambiguous CFG of size} < n} {\# \text{ CFG of size} < n}$$

where terminal and non-terminal symbols come from a fixed countable set.

The size of a grammar is any reasonable notion of size for grammars, e.g.

  1. the total number of occurrences of variables and terminals in the production rules, or
  2. the total number of occurrences of variable, or
  3. the total number of production rules, or
  4. the number of distinct variables.

(I am assuming the definition of size will not affect the answer.)

Improve this question
$\endgroup$
37
  • 3
    $\begingroup$ As an aside, the following notions of CFG size have been considered in the literature: As to notions of grammar size, the following have appeared in the literature. (1) Total number of occurrences of variables and terminals on both sides of all productions in the grammar. (2) Number of variable occurrences on both sides of all productions in the grammar. (3) Number of productions in the grammar. (4) Number of distinct variables in the grammar. $\endgroup$
    – Martin Berger
    Commented Jun 4, 2014 at 8:18
  • 1
    $\begingroup$ See for example: S. Ginsburg, N. Lynch, Size Complexity in Context-Free Grammar Forms. J. Gruska, On the size of context-free grammars. J. Gruska, Complexity and Unambiguity of Context-Free Grammars and Languages. A. Kelemenova, Complexity Of Normal Form Grammars. $\endgroup$
    – Martin Berger
    Commented Jun 4, 2014 at 8:19
  • 1
    $\begingroup$ @Martin, if one is not careful then there can be infinitely many syntacticly different grammars of a given size and the ratio will not make sense. The safe way is to count the bit length of some fixed encoding of grammars. $\endgroup$
    – Kaveh
    Commented Jun 5, 2014 at 0:35
  • 1
    $\begingroup$ You probably want to define the asymptotic density as the ratio of logarithms of the respective quantities, since both quantities are exponential, probably with different bases. $\endgroup$
    – greg
    Commented Jun 5, 2014 at 13:01
  • 1
    $\begingroup$ @MartinBerger Assuming we're talking about the same thing, i.e. defining $logdensity = log(\#unambiguousCFGs) / log(\#CFGs)$, this would obviously affect the density. Suppose that the number of unambiguous CFGs is $1.5^n$ and the number of CFGs is $2^n$, then the log-density is $log_{1.5} 2$ while the asymptotic density is 0. I'm pretty sure that the asymptotic density will be either 0 or 1, but the asymptotic log-density is likely to be an interesting number. $\endgroup$
    – greg
    Commented Jun 5, 2014 at 15:41

1 Answer 1

Reset to default
4
$\begingroup$

The question depends on the exact encoding. However, it seems that in many reasonable encodings, as the length tends to infinity, the number of production rules $S\to a$ (for an appropriate interpretation of the starting symbol $S$ and the terminal $a$) will be more than one with high probability; here I literally mean the same terminal $a$. If we consider this as ambiguity, then I expect "most" grammars to be ambiguous. We can also concoct similar situations such as the rules $S\to S$ and $S\to a$ each appearing at least once.

Assuming this general hypothesis, that every (fixed) conceivable rule should appear with high probability as the length tends to infinity, we find that "most" grammars generate $\Sigma^*$ in an ambiguous manner.

As an example, consider the following encoding for grammars over $\Sigma = \{0,1\}$. The grammar alphabet consists of the symbols $\{0,1,;,.\}$. Non-terminals are indexed by binary strings of length at least 2. Rules are separated by full stops. Each rule is a sequence of binary strings separated by semicolons. The first binary string is the non-terminal on the left-hand side, and the rest (if any) constitute the right-hand side; if the first binary string is not a non-terminal (i.e., it is $\epsilon$,0,1), then the starting non-terminal is assumed. The starting non-terminal is always 00.

Under this encoding, every string in $\{0,1,;,.\}^*$ describes some grammar. A random grammar will with high probability contain many copies of $.00;00.$ and $.00;0.$, and in particular will be ambiguous.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Yes, I do consider rules such as $S\to S$ and $S\to a$ (appearing more than once) in a grammar as valid. Indeed, this makes a grammar trivially ambiguous. Cheers. $\endgroup$
    – user18064
    Commented Jun 6, 2014 at 22:06
  • $\begingroup$ But isn't it also the case that, as size(CFG) increases, the number of terminals and non-terminals typically increases, so we need more bits to represent them, hence we need more bits to represent individual rules. So the number of CFGs which are unambiguous for trivial reasons (e.g. only one rule fits into the size bound) also increases. $\endgroup$
    – Martin Berger
    Commented Jun 7, 2014 at 10:22
  • $\begingroup$ @Martin It depends on the encoding. Perhaps you can come up with an encoding supporting your claim, for example if the alphabet size grows with the grammar size. My encoding uses a constant alphabet size, so this effect doesn't happen. $\endgroup$
    – Yuval Filmus
    Commented Jun 7, 2014 at 14:47
  • $\begingroup$ @MartinBerger That is a valid point about increasing the number of terminal and non-terminal symbols as we increase the grammar size. For use cases such as programming languages, that makes sense. $\endgroup$
    – user18064
    Commented Jun 7, 2014 at 23:25
  • $\begingroup$ @user18064 Programming languages usually use a constant-size alphabet, in most cases a subset of ASCII. I'm not aware of any practical language with unlimited alphabet size, though one could easily define them. $\endgroup$
    – Yuval Filmus
    Commented Jun 8, 2014 at 5:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.