<p>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 <em>same</em> 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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-06-06T22:06:34.250Z
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.
user18064
CC BY-SA 3.0
2014-06-07T10:22:50.457Z
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.
Martin Berger
CC BY-SA 3.0
2014-06-07T14:47:12.583Z
@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.
Yuval Filmus
CC BY-SA 3.0
2014-06-07T23:25:40.060Z
@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.
user18064
CC BY-SA 3.0
2014-06-08T05:56:10.920Z
@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.
Yuval Filmus
CC BY-SA 3.0
2014-06-08T09:46:26.833Z
@YuvalFilmus The effect already happens with $\{0,1\}$ as alphabet. To
see why consider a string $\sigma \in \{0,1\}^*$ of length $n$. Then
the string $00;\sigma$ is a CFG of size $n+3$ that is trivially
unambiguous because it has only one rule. There are $2^n$ of those at
size $n+3$. That's an exponential growth. Is it totally obvious that
the growth-rate of trivially ambiguous CFGs always outpaces the growth
of trivially unambiguous CFGs?  For any CFG with a trivial rule, say
$00;0.\sigma;\gamma$ there is a corresponding CFG $00;00\sigma
0\gamma$ of the same size but with one rule less.
Martin Berger
CC BY-SA 3.0
2014-06-08T10:38:04.477Z
@YuvalFilmus The encoding also 'privileges' CFGs with lots of short
rules because it is sensitive to rule ordering: 00;0.00;1 is counted
as a different CFG from 00;1.00;0. But rule ordering has no bearing on
ambiguity, so rule ordering needs to be modded out. Likewise 00;0 and
00;0.00;0 are counted as two different CFGs under this encoding, even
though 'set theoretically' they are the same.
Martin Berger
CC BY-SA 3.0
2014-06-08T19:45:58.300Z
@MartinBerger I've presented what I consider to be a natural distribution, which for trivial reasons favors ambiguity. If you have any other distribution on CFGs in mind, then you can present it formally and all of us can try to analyze it.
Yuval Filmus
CC BY-SA 3.0
2014-06-08T21:47:33.727Z
@YuvalFilmus I'm using *your* encoding. One of the things I'm saying is that it's unclear to me that in your encoding the trivially ambiguous grammars outnumber (in the limit) the trivially unambiguous grammars.
Martin Berger
CC BY-SA 3.0
2014-06-09T22:36:01.917Z
@YuvalFilmus It seems I didn't explain very well with my previous comment on increasing the number of terminals as the grammar size increases. Apologies. What I meant to say was that there is a balance between the number of non-terminals to the number of terminals for PL grammars. Increasing the grammar size, should proportionately increase both the number of non-terminals and the number of terminals. My observation on looking at various grammar metrics for PL grammars is that the ratio of number(non-terminals):number(terminals) is roughly 1:1. Have you included this in your encoding? Cheers.
user18064
CC BY-SA 3.0
2014-06-10T01:25:25.017Z
@user18064 If you have any concrete probability distribution on grammars in mind (parametrized by a length parameter), then we can all try to analyze it. Perhaps the real question here is what is a good distribution on context-free grammars.
Yuval Filmus
CC BY-SA 3.0
2014-06-06T06:35:17.070Z
2014-06-06T06:35:17.070Z
Yuval Filmus
<p>What is the ratio of <a href="https://en.wikipedia.org/wiki/Ambiguous_grammar" rel="nofollow">ambiguous</a> CFGs to all <a href="https://en.wikipedia.org/wiki/Context-free_grammar" rel="nofollow">CFGs</a>? </p>

<p>Since both sets are countably infinite the ratio is not well-defined. 
But what about the <a href="https://en.wikipedia.org/wiki/Natural_density" rel="nofollow">asymptotic density</a>:</p>

<p>$$\lim_{n \mapsto \infty}\frac
  {\# \text{ ambiguous CFG of size} &lt; n}
  {\# \text{ CFG of size} &lt; n}$$</p>

<p>where terminal and non-terminal symbols come from a fixed countable set. </p>

<p>The size of a grammar is any reasonable notion of size for grammars, e.g.</p>

<ol>
<li>the total number of occurrences of variables and terminals in the production rules, or</li>
<li>the total number of occurrences of variable, or </li>
<li>the total number of production rules, or</li>
<li>the number of distinct variables.</li>
</ol>

<p>(I am assuming the definition of size will not affect the answer.)</p>

CC BY-SA 3.0
2014-06-02T07:18:52.150Z
Defining the size of a *grammar* doesn't affect the question because the question is about size of *sets of grammars*. However you define the size of a grammar, as pointed out in @D.W.'s [answer](http://cs.stackexchange.com/a/26258/9550), there are a countable infinity of grammars of all the interesting kinds. The number of, say, unambiguous grammars doesn't depend on how you define the size of a grammar.
David Richerby
CC BY-SA 3.0
2014-06-02T07:20:11.200Z
@DavidRicherby, defining the size of a grammar is potentially relevant because the original poster suggested in a comment that we might look at the set of grammars of size $\le n$ (see the 2nd comment from the top) -- my comment was a response to that.  You'll need to read the entire comment thread to understand why I made that comment.
D.W.
CC BY-SA 3.0
2014-06-03T15:22:12.727Z
Defining a size for grammars allows you to count all grammars of a given size (there will be finitely many for a given alphabet).  E.g. the total number of symbols in left hand sizes and right hand sizes seems a reasonable definition of size. There is still the question to what extent you'd want to deduplicate the resulting sets (is S -> aS | b the same grammar as T -> bT | c?) but several variants could be studied and compared.
reinierpost
CC BY-SA 3.0
2014-06-04T08:18:37.463Z
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.
Martin Berger
CC BY-SA 3.0
2014-06-04T08:19:15.757Z
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.
Martin Berger
CC BY-SA 3.0
2014-06-04T08:20:04.383Z
I conjecture that the asymptotic density of ambiguous CFGs among all CFGs is the same for all four notions of size.
Martin Berger
CC BY-SA 3.0
2014-06-05T00:35:44.510Z
@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.
Kaveh
CC BY-SA 3.0
2014-06-05T01:50:55.233Z
("SWAG") conjecture, there are "more" ambiguous CFLs than unambiguous ones and the "density" of unambiguous ones approaches zero in the limit. note that some CFLs admit both [ambiguous](http://en.wikipedia.org/wiki/Ambiguous_grammar) and unambiguous grammars! so the question prob needs to be technically rephrased to [inherently ambiguous](http://en.wikipedia.org/wiki/Ambiguous_grammar#Inherently_ambiguous_languages) grammars.
vzn
CC BY-SA 3.0
2014-06-05T06:17:06.410Z
@Kaveh Yes, one needs to be careful with coding.
Martin Berger
CC BY-SA 3.0
2014-06-05T06:17:44.310Z
@vzn Judging by the previous version of the question before its move
to cstheory, I don't think the user18064 is interested in inherent
ambiguity, but rather in the density of ambiguous CFGs in CFGs. The
density of inherently ambiguous languages in CFLs or in ambiguous CFLs
is a different, but also interesting question.
Martin Berger
CC BY-SA 3.0
2014-06-05T09:32:19.687Z
Since ambiguity is undecidable, this question is probably not easy to
answer.  Maybe one way towards answerting this question to look at the
density of ambiguous regular expressions in regular expressions.
Moreover, there are probably fewer natural ways of defining a notion
of size for regular expressions.
Martin Berger
CC BY-SA 3.0
2014-06-05T13:01:34.733Z
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.
greg
CC BY-SA 3.0
2014-06-05T15:12:45.107Z
@mobiusdumpling In what sense would using logarithmic density affect the limits?
Martin Berger
CC BY-SA 3.0
2014-06-05T15:14:03.450Z
every CFG has a corresponding CFL and "technically" [every CFL has an ambiguous CFG](http://cs.stackexchange.com/questions/26422/does-every-cfl-have-an-ambiguous-cfg) (actually _many/infinitely_ such ambiguous CFGs) & so not totally sure this question is phrased in a meaningful/coherent way.... also & in other words the same CFL can be represented in different ways which the problem seems not to take into account.... also on search there are complex papers looking at "density in CFLs" but it seems all _word count/density_ in given CFLs so far.
vzn
CC BY-SA 3.0
2014-06-05T15:16:13.557Z
@vzn From the original question I got the feeling that user18064 is interested in parsing and has written 'Monte-Carlo'-like algorithms that seek to decide quickly (and approximatively) if a given CFG is ambiguous or not. In this context questions about ambiguity of CFLs might lead in a different direction.
Martin Berger
CC BY-SA 3.0
2014-06-05T15:21:00.707Z
user18064 has disappeared for the moment and suspect s/hes a nonresearcher, possibly undergraduate, luckily hitting on an potentially intriguing abstract question that maybe hasnt been studied (& lets not speculate too much lacking any response/clarification), but still am not convinced it has been formulated in a meaningful way. the idea of a monte carlo simulation is interesting & possibly related somehow but note that [recognizing ambiguous CFGs is undecidable!](http://en.wikipedia.org/wiki/Ambiguous_grammar#Recognizing_ambiguous_grammars)
vzn
CC BY-SA 3.0
2014-06-05T15:41:02.110Z
@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.
greg
CC BY-SA 3.0
2014-06-05T15:41:57.717Z
re undecidability of ambiguous CFG detection, therefore this question seems vaguely similar to asking about probability of random TMs halting! re [chaitins constant](http://en.wikipedia.org/wiki/Chaitin's_constant)...(which is incomputable!) in both cases its random strings, some of which may denote an "undecidable instance"....
vzn
CC BY-SA 3.0
2014-06-05T16:01:58.800Z
@mobiusdumpling
Thanks, that's a great point. I conjecture that the asymptotic density is 1.
Even being able to verify this would be interesting. But I agree, if the growth rate
of both sets is exponential, logarithmic density would be a more refined result. I guess
it would also be harder to establish. Have you got any intuitions how to prove (or at least approach) either?
Martin Berger
CC BY-SA 3.0
2014-06-05T16:03:06.547Z
@vzn The question is perfectly well-defined (except for being open about how to measure CFG-size), and user18064's original
question linked to his publications on randomised ambiguity detection.
Martin Berger
CC BY-SA 3.0
2014-06-05T16:38:09.683Z
@Martin ??? the question has indeed been heavily edited thx for the tip (& gone thru migration from cs.se also etc) but [rev1](http://cstheory.stackexchange.com/revisions/23784/1) has no such ref to "his publications on randomised ambiguity detection" & the users profile on cs.se has no further detail (its "his" 1st question), are you refing to some other se question somewhere else (other site?) by the same user? also am not aware of any instances of asymptotic density concept being applied to a "language" where individual instances may not be computable ie a recursively enumerable language...
vzn
CC BY-SA 3.0
2014-06-05T17:02:28.503Z
@vzn Asymptotic density has nothing to do with computability. It's
just a limit of real numbers, more specifically of
probabilities. So it's a concept from real analysis. Of course
that limit might not be a computable real number. So what? That's an orthogonal matter. One may of course ask what computable strength densities
have,  depending on where in hierarchy of computability the sets
sit over which we take the density, see e.g. [Asymptotic Density
And Computably Enumerable Sets](http://arxiv.org/abs/1307.0040).
Martin Berger
CC BY-SA 3.0
2014-06-05T17:07:23.297Z
@vzn https://cs.stackexchange.com/posts/26256/revisions
Martin Berger
CC BY-SA 3.0
2014-06-05T22:03:12.807Z
MB ok thx it is as you stated (he deleted his own refs in rev4 & tcs.se revision history omits the cs.se history) & here is his [home page (Naveneetha K Vasudevan)](http://navkrish.net/) with the papers at Kings College London but something seems off if he seems to write as if he has a tool to _computably_ determine ambiguous grammars...! cs.se [rev2](https://cs.stackexchange.com/revisions/26256/2): "The results from my experiment -- where I run my ambiguity checker tool against these grammar sets -- seem to indicate that ~90% of the grammars are ambiguous."
vzn
CC BY-SA 3.0
2014-06-05T22:17:59.230Z
@vzn Apologies for various edits. This could have been avoided. I was merely indicating that most grammars were ambiguous. It is also the case that other ambiguity checker tools ([AmbiDexter](https://sites.google.com/site/basbasten/ambiguity) and [AMBER](http://accent.compilertools.net/Amber.html)) also found most similar-ish results.
user18064
CC BY-SA 3.0
2014-06-05T22:33:59.390Z
@user18064 maybe further this in [chat]? [np on revs, understand some are often in response/reaction to random critical comments.] but dont the tools sometimes return inconclusive results on this fundamentally undecidable problem, so isnt there no concept of empirically measurable results? you acknowledge its undecidability in slides/papers on your site... (only other conceivable possibility seems that the instances are too "small" to be undecidable or biased in some other way but that seems unlikely also...)
vzn
CC BY-SA 3.0
2014-06-05T22:41:40.693Z
@vzn Yes, ambiguity detection is an undecidable problem. It is likely that my grammar generating tool could be biased. That is, it may have a higher chance of generating ambiguous grammars. I have no way of measuring this. I have acknowledged this weakness in my post at cs.se [rev2](https://cs.stackexchange.com/revisions/26256/2). Perhaps, there are other grammar generating methods (that I am not aware of), for which these tools may return inconclusive results.
user18064
CC BY-SA 3.0
2014-06-05T22:45:15.453Z
@vzn Cheers for the reference to tcs chat.
user18064
CC BY-SA 3.0
2014-06-05T23:01:13.083Z
@user18064 / NV if you have a large random sample of small languages that _all_ can be resolved as either ambiguous/unambiguous _(without discarding any),_ that alone seems like an experimental and possibly even theoretical breakthrough....! note that re other undecidable problems eg [busy beaver](http://en.wikipedia.org/wiki/Busy_beaver) even very small instances (machine encodings) are inconclusive. are there any other such empirical studies you know of for CFLs ambiguity analysis? havent heard of any.... maybe yours is groundbreaking?
vzn
CC BY-SA 3.0
2014-06-06T11:11:50.880Z
@vzn I am not aware of any empirical studies involving large sample of grammars, where it has been proven the decidability of ambiguity/unambiguity even for small instances. Although my ambiguity checker tool uncovers ambiguity for most of the random grammars very quickly, it is likely that if I were to leave my tool running for few days, it will uncover more ambiguities. So, I am afraid the problem is still undecidable even for small instances.
user18064
CC BY-SA 3.0
2014-06-06T15:14:29.210Z
@user18064 / NV from your last comment am thinking maybe your "~90%" figure is technically a _lower_ bound on ambiguous language count. does it increase the longer you run the code? that is what you seem to be saying. if so then "remainders" are similar to the concept of "holdouts" in busy beaver research ie unresolved/inconclusive instances....
vzn
CC BY-SA 3.0
2014-06-06T17:05:58.557Z
@vzn Yes, that ~90% figure is lower bound. If I leave it running for few days, the number of ambiguities found only increases marginally. Cheers for the reference to busy beaver problem. I wasn't aware of that problem.
user18064
CC BY-SA 3.0
2014-06-07T16:48:52.547Z
NV so it sounds like the code runs in _parallel_ across all the initially generated CFG instances and as it runs, some instances out of the whole set are determined ambiguous? can it also resolve some instances as unambiguous? and some remain as "unfinished/ nonterminated" etc? that is roughly how some busy beaver research algorithms are formulated...
vzn
CC BY-SA 3.0
2014-06-07T23:41:40.310Z
@vzn my ambiguity checker tool does not resolve CFG instances as unambiguous. So, it is either ambiguous or unfinished.
user18064
CC BY-SA 3.0
2014-06-08T01:04:19.193Z
ok thx for all the info. hope you write up these results, these types of investigations seem relatively rare & yet seem quite worthwhile in pushing the state of the art. only one more suggestion, wouldnt it remove some of the objections or wrinkles about encodings to study the question for CFLs instead of CFGs?
vzn
CC BY-SA 3.0
2014-06-08T09:21:21.130Z
@vzn You can't get away from encodings because CFLs are typically infinite objects that you need to represent finitely, for example by a CFG.
Martin Berger
CC BY-SA 3.0
2014-06-08T15:36:50.147Z
_oops_ ok further thought, forgot CFG equivalence is undecidable (which would be reqd to differentiate _unique_ CFLs...). NV, one other idea, seems like "from the other direction" there could be CFG testers that can prove unambiguity for some instances (in contrast) & that maybe those could be combined with a ambiguity prover to obtain superior accuracy measurements?
vzn
<fl.formal-languages><grammars><context-free>
Asymptotic density of ambiguous context-free grammars (CFGs)
user18064
# Asymptotic density of ambiguous context-free grammars (CFGs)

(Asked by: username_0 on 2014-05-30)

What is the ratio of [ambiguous](https://en.wikipedia.org/wiki/Ambiguous_grammar) CFGs to all [CFGs](https://en.wikipedia.org/wiki/Context-free_grammar)?

Since both sets are countably infinite the ratio is not well-defined.
But what about the [asymptotic density](https://en.wikipedia.org/wiki/Natural_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.)

**Tags:** fl.formal-languages, grammars, context-free
> **Comments:**
> **username_1**: Defining the size of a *grammar* doesn't affect the question because the question is about size of *sets of grammars*. However you define the size of a grammar, as pointed out in @D.W.'s [answer](http://cs.stackexchange.com/a/26258/9550), there are a countable infinity of grammars of all the interesting kinds. The number of, say, unambiguous grammars doesn't depend on how you define the size of a grammar.  
> **username_2**: @DavidRicherby, defining the size of a grammar is potentially relevant because the original poster suggested in a comment that we might look at the set of grammars of size $\le n$ (see the 2nd comment from the top) -- my comment was a response to that.  You'll need to read the entire comment thread to understand why I made that comment.  
> **username_3**: Defining a size for grammars allows you to count all grammars of a given size (there will be finitely many for a given alphabet).  E.g. the total number of symbols in left hand sizes and right hand sizes seems a reasonable definition of size. There is still the question to what extent you'd want to deduplicate the resulting sets (is S -> aS | b the same grammar as T -> bT | c?) but several variants could be studied and compared.  
> **username_4**: 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.  
> **username_4**: 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.  
> **username_4**: I conjecture that the asymptotic density of ambiguous CFGs among all CFGs is the same for all four notions of size.  
> **username_5**: @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.  
> **username_6**: ("SWAG") conjecture, there are "more" ambiguous CFLs than unambiguous ones and the "density" of unambiguous ones approaches zero in the limit. note that some CFLs admit both [ambiguous](http://en.wikipedia.org/wiki/Ambiguous_grammar) and unambiguous grammars! so the question prob needs to be technically rephrased to [inherently ambiguous](http://en.wikipedia.org/wiki/Ambiguous_grammar#Inherently_ambiguous_languages) grammars.  
> **username_4**: @Kaveh Yes, one needs to be careful with coding.  
> **username_4**: @vzn Judging by the previous version of the question before its move to cstheory, I don't think the user18064 is interested in inherent ambiguity, but rather in the density of ambiguous CFGs in CFGs. The density of inherently ambiguous languages in CFLs or in ambiguous CFLs is a different, but also interesting question.  
> **username_4**: Since ambiguity is undecidable, this question is probably not easy to answer.  Maybe one way towards answerting this question to look at the density of ambiguous regular expressions in regular expressions. Moreover, there are probably fewer natural ways of defining a notion of size for regular expressions.  
> **username_7**: 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.  
> **username_4**: @mobiusdumpling In what sense would using logarithmic density affect the limits?  
> **username_6**: every CFG has a corresponding CFL and "technically" [every CFL has an ambiguous CFG](http://cs.stackexchange.com/questions/26422/does-every-cfl-have-an-ambiguous-cfg) (actually _many/infinitely_ such ambiguous CFGs) & so not totally sure this question is phrased in a meaningful/coherent way.... also & in other words the same CFL can be represented in different ways which the problem seems not to take into account.... also on search there are complex papers looking at "density in CFLs" but it seems all _word count/density_ in given CFLs so far.  
> **username_4**: @vzn From the original question I got the feeling that user18064 is interested in parsing and has written 'Monte-Carlo'-like algorithms that seek to decide quickly (and approximatively) if a given CFG is ambiguous or not. In this context questions about ambiguity of CFLs might lead in a different direction.  
> **username_6**: user18064 has disappeared for the moment and suspect s/hes a nonresearcher, possibly undergraduate, luckily hitting on an potentially intriguing abstract question that maybe hasnt been studied (& lets not speculate too much lacking any response/clarification), but still am not convinced it has been formulated in a meaningful way. the idea of a monte carlo simulation is interesting & possibly related somehow but note that [recognizing ambiguous CFGs is undecidable!](http://en.wikipedia.org/wiki/Ambiguous_grammar#Recognizing_ambiguous_grammars)  
> **username_7**: @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.  
> **username_6**: re undecidability of ambiguous CFG detection, therefore this question seems vaguely similar to asking about probability of random TMs halting! re [chaitins constant](http://en.wikipedia.org/wiki/Chaitin's_constant)...(which is incomputable!) in both cases its random strings, some of which may denote an "undecidable instance"....  
> **username_4**: @mobiusdumpling Thanks, that's a great point. I conjecture that the asymptotic density is 1. Even being able to verify this would be interesting. But I agree, if the growth rate of both sets is exponential, logarithmic density would be a more refined result. I guess it would also be harder to establish. Have you got any intuitions how to prove (or at least approach) either?  
> **username_4**: @vzn The question is perfectly well-defined (except for being open about how to measure CFG-size), and user18064's original question linked to his publications on randomised ambiguity detection.  
> **username_6**: @Martin ??? the question has indeed been heavily edited thx for the tip (& gone thru migration from cs.se also etc) but [rev1](http://cstheory.stackexchange.com/revisions/23784/1) has no such ref to "his publications on randomised ambiguity detection" & the users profile on cs.se has no further detail (its "his" 1st question), are you refing to some other se question somewhere else (other site?) by the same user? also am not aware of any instances of asymptotic density concept being applied to a "language" where individual instances may not be computable ie a recursively enumerable language...  
> **username_4**: @vzn Asymptotic density has nothing to do with computability. It's just a limit of real numbers, more specifically of probabilities. So it's a concept from real analysis. Of course that limit might not be a computable real number. So what? That's an orthogonal matter. One may of course ask what computable strength densities have,  depending on where in hierarchy of computability the sets sit over which we take the density, see e.g. [Asymptotic Density And Computably Enumerable Sets](http://arxiv.org/abs/1307.0040).  
> **username_4**: @vzn https://cs.stackexchange.com/posts/26256/revisions  
> **username_6**: MB ok thx it is as you stated (he deleted his own refs in rev4 & tcs.se revision history omits the cs.se history) & here is his [home page (Naveneetha K Vasudevan)](http://navkrish.net/) with the papers at Kings College London but something seems off if he seems to write as if he has a tool to _computably_ determine ambiguous grammars...! cs.se [rev2](https://cs.stackexchange.com/revisions/26256/2): "The results from my experiment -- where I run my ambiguity checker tool against these grammar sets -- seem to indicate that ~90% of the grammars are ambiguous."  
> **username_0**: @vzn Apologies for various edits. This could have been avoided. I was merely indicating that most grammars were ambiguous. It is also the case that other ambiguity checker tools ([AmbiDexter](https://sites.google.com/site/basbasten/ambiguity) and [AMBER](http://accent.compilertools.net/Amber.html)) also found most similar-ish results.  
> **username_6**: @user18064 maybe further this in [chat]? [np on revs, understand some are often in response/reaction to random critical comments.] but dont the tools sometimes return inconclusive results on this fundamentally undecidable problem, so isnt there no concept of empirically measurable results? you acknowledge its undecidability in slides/papers on your site... (only other conceivable possibility seems that the instances are too "small" to be undecidable or biased in some other way but that seems unlikely also...)  
> **username_0**: @vzn Yes, ambiguity detection is an undecidable problem. It is likely that my grammar generating tool could be biased. That is, it may have a higher chance of generating ambiguous grammars. I have no way of measuring this. I have acknowledged this weakness in my post at cs.se [rev2](https://cs.stackexchange.com/revisions/26256/2). Perhaps, there are other grammar generating methods (that I am not aware of), for which these tools may return inconclusive results.  
> **username_0**: @vzn Cheers for the reference to tcs chat.  
> **username_6**: @user18064 / NV if you have a large random sample of small languages that _all_ can be resolved as either ambiguous/unambiguous _(without discarding any),_ that alone seems like an experimental and possibly even theoretical breakthrough....! note that re other undecidable problems eg [busy beaver](http://en.wikipedia.org/wiki/Busy_beaver) even very small instances (machine encodings) are inconclusive. are there any other such empirical studies you know of for CFLs ambiguity analysis? havent heard of any.... maybe yours is groundbreaking?  
> **username_0**: @vzn I am not aware of any empirical studies involving large sample of grammars, where it has been proven the decidability of ambiguity/unambiguity even for small instances. Although my ambiguity checker tool uncovers ambiguity for most of the random grammars very quickly, it is likely that if I were to leave my tool running for few days, it will uncover more ambiguities. So, I am afraid the problem is still undecidable even for small instances.  
> **username_6**: @user18064 / NV from your last comment am thinking maybe your "~90%" figure is technically a _lower_ bound on ambiguous language count. does it increase the longer you run the code? that is what you seem to be saying. if so then "remainders" are similar to the concept of "holdouts" in busy beaver research ie unresolved/inconclusive instances....  
> **username_0**: @vzn Yes, that ~90% figure is lower bound. If I leave it running for few days, the number of ambiguities found only increases marginally. Cheers for the reference to busy beaver problem. I wasn't aware of that problem.  
> **username_6**: NV so it sounds like the code runs in _parallel_ across all the initially generated CFG instances and as it runs, some instances out of the whole set are determined ambiguous? can it also resolve some instances as unambiguous? and some remain as "unfinished/ nonterminated" etc? that is roughly how some busy beaver research algorithms are formulated...  
> **username_0**: @vzn my ambiguity checker tool does not resolve CFG instances as unambiguous. So, it is either ambiguous or unfinished.  
> **username_6**: ok thx for all the info. hope you write up these results, these types of investigations seem relatively rare & yet seem quite worthwhile in pushing the state of the art. only one more suggestion, wouldnt it remove some of the objections or wrinkles about encodings to study the question for CFLs instead of CFGs?  
> **username_4**: @vzn You can't get away from encodings because CFLs are typically infinite objects that you need to represent finitely, for example by a CFG.  
> **username_6**: _oops_ ok further thought, forgot CFG equivalence is undecidable (which would be reqd to differentiate _unique_ CFLs...). NV, one other idea, seems like "from the other direction" there could be CFG testers that can prove unambiguity for some instances (in contrast) & that maybe those could be combined with a ambiguity prover to obtain superior accuracy measurements?  

---

## 1 answers

### Answer by username_8 on 2014-06-06. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_4**: 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.  
> **username_8**: @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.  
> **username_0**: @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.  
> **username_8**: @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.  
> **username_4**: @YuvalFilmus The effect already happens with $\{0,1\}$ as alphabet. To see why consider a string $\sigma \in \{0,1\}^*$ of length $n$. Then the string $00;\sigma$ is a CFG of size $n+3$ that is trivially unambiguous because it has only one rule. There are $2^n$ of those at size $n+3$. That's an exponential growth. Is it totally obvious that the growth-rate of trivially ambiguous CFGs always outpaces the growth of trivially unambiguous CFGs?  For any CFG with a trivial rule, say $00;0.\sigma;\gamma$ there is a corresponding CFG $00;00\sigma 0\gamma$ of the same size but with one rule less.  
> **username_4**: @YuvalFilmus The encoding also 'privileges' CFGs with lots of short rules because it is sensitive to rule ordering: 00;0.00;1 is counted as a different CFG from 00;1.00;0. But rule ordering has no bearing on ambiguity, so rule ordering needs to be modded out. Likewise 00;0 and 00;0.00;0 are counted as two different CFGs under this encoding, even though 'set theoretically' they are the same.  
> **username_8**: @MartinBerger I've presented what I consider to be a natural distribution, which for trivial reasons favors ambiguity. If you have any other distribution on CFGs in mind, then you can present it formally and all of us can try to analyze it.  
> **username_4**: @YuvalFilmus I'm using *your* encoding. One of the things I'm saying is that it's unclear to me that in your encoding the trivially ambiguous grammars outnumber (in the limit) the trivially unambiguous grammars.  
> **username_0**: @YuvalFilmus It seems I didn't explain very well with my previous comment on increasing the number of terminals as the grammar size increases. Apologies. What I meant to say was that there is a balance between the number of non-terminals to the number of terminals for PL grammars. Increasing the grammar size, should proportionately increase both the number of non-terminals and the number of terminals. My observation on looking at various grammar metrics for PL grammars is that the ratio of number(non-terminals):number(terminals) is roughly 1:1. Have you included this in your encoding? Cheers.  
> **username_8**: @user18064 If you have any concrete probability distribution on grammars in mind (parametrized by a length parameter), then we can all try to analyze it. Perhaps the real question here is what is a good distribution on context-free grammars.  

---

