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.the total number of occurrences of variables and terminals in the production rules, orthe total number of occurrences of variable, or the total number of production rules, orthe number of distinct variables.(I am assuming the definition of size will not affect the answer.)
Asymptotic density of ambiguous context-free grammars (CFGs)
fl.formal languages;grammars;context free
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.