5
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ also sparked somewhat on pondering this tcs.se question asking about density of ambiguous CFGs $\endgroup$ – vzn Jun 5 '14 at 15:15
11
$\begingroup$

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*} $$

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

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ so in other words every CFL except the empty language has infinite associated ambiguous grammars? $\endgroup$ – vzn Jun 5 '14 at 15:24
  • $\begingroup$ Is this still true if $\epsilon$ transitions are permitted? For example $S \rightarrow \epsilon | S$ seems ambiguous to me. $\endgroup$ – Wandering Logic Jun 5 '14 at 16:14
  • 3
    $\begingroup$ @WanderingLogic Your example (ambiguously) generates $\{ \epsilon \}$, which is not the empty set. $\endgroup$ – Hendrik Jan Jun 5 '14 at 19:30
  • $\begingroup$ A slight problem with the statement though is that its truth is vacuous. It has no strings, so any statement about the strings it has is necessarily true. It is also equally true that it has no strings for which there is a unique derivation tree. This makes it important how exactly "ambiguous grammar" is defined. $\endgroup$ – Tim Seguine Mar 30 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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