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?
does every CFL have an ambiguous CFG?
formal languages;formal grammars;ambiguity
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*}$$