Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

some questions have been popping up recently on ambiguity in CFLs/CFGs which can have subtleties (eg languages vs grammars & ambiguity vs inherent ambiguity). wikipedia states:

Many [context free?] languages admit both ambiguous and unambiguous grammars, while some languages admit only ambiguous grammars.

the sentence is phrased in wikipedia without the "CFL" inserted but am now wondering what effect it has on the logic. after pondering the technical defn of ambiguity (on wikipedia pg) & thinking about it a bit my question:

does every CFL have an ambiguous CFG? if not what is a counterexample ie a CFL that does not have (any) ambiguous CFG?

(the question arose in that every CFL has multiple CFGs, ie a CFG is only unique to a CFL under additional restrictions, and it seems that given any (unambiguous) CFG one could add small chgs/productions rules to get an equivalent ambiguous CFG...? is this trivial? but rarely pointed out anywhere?)

somewhat related question somewhat involved in sparking this one: Are there inherently ambiguous and deterministic context-free languages?

share|cite|improve this question
also sparked somewhat on pondering this question asking about density of ambiguous CFGs – vzn Jun 5 '14 at 15:15
up vote 10 down vote accepted

Every nonempty context-free language has an ambiguous grammar. Consider any context-free grammar for the language with starting symbol $S$. We add new non-terminals $S',A',B'$, make $S'$ the new starting symbol, and add the following rules: $$ \begin{align*} &S' \to A' \\ &S' \to B' \\ &A' \to S \\ &B' \to S \end{align*} $$

share|cite|improve this answer
Adding $S\to S$ will do. – Hendrik Jan Jun 5 '14 at 11:20

The following statement seems mathematically correct, though confusing.

Any grammar for the empty language $\varnothing$ is unambiguous: it has no strings for which there are two different valid derivation trees.

share|cite|improve this answer
so in other words every CFL except the empty language has infinite associated ambiguous grammars? – vzn Jun 5 '14 at 15:24
Is this still true if $\epsilon$ transitions are permitted? For example $S \rightarrow \epsilon | S$ seems ambiguous to me. – Wandering Logic Jun 5 '14 at 16:14
@WanderingLogic Your example (ambiguously) generates $\{ \epsilon \}$, which is not the empty set. – Hendrik Jan Jun 5 '14 at 19:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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