Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
    
also sparked somewhat on pondering this tcs.se question asking about density of ambiguous CFGs –  vzn Jun 5 at 15:15

2 Answers 2

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|improve this answer
4  
Adding $S\to S$ will do. –  Hendrik Jan Jun 5 at 11:20
    
See Hendrik's answer below; I think he's actually correct, and you might consider editing this answer to include that information. –  Patrick87 Jun 5 at 18:32
    
@Patrick87 Somebody already corrected my answer for me; read the second word. –  Yuval Filmus Jun 6 at 0:40

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|improve this answer
1  
so in other words every CFL except the empty language has infinite associated ambiguous grammars? –  vzn Jun 5 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 at 16:14
1  
@WanderingLogic Your example (ambiguously) generates $\{ \epsilon \}$, which is not the empty set. –  Hendrik Jan Jun 5 at 19:30

Your Answer

 
discard

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.