Editing Ambiguous grammar (section)

== Inherently ambiguous languages ==
While some context-free languages (the set of strings that can be generated by a grammar) have both ambiguous and unambiguous grammars, there exist context-free languages for which no unambiguous context-free grammar exists. Such languages are called '''inherently ambiguous'''.

There are no inherently ambiguous regular languages.<ref>{{Cite journal |last1=Book |first1=R. |last2=Even |first2=S. |last3=Greibach |first3=S. |last4=Ott |first4=G. |date=Feb 1971 |title=Ambiguity in Graphs and Expressions |url=http://dx.doi.org/10.1109/t-c.1971.223204 |journal=IEEE Transactions on Computers |volume=C-20 |issue=2 |pages=149–153 |doi=10.1109/t-c.1971.223204 |s2cid=20676251 |issn=0018-9340|url-access=subscription }}</ref><ref>{{Cite web |title=formal languages - Can regular expressions be made unambiguous? |url=https://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous |access-date=2023-02-23 |website=MathOverflow |language=en}}</ref>

The existence of inherently ambiguous context-free languages was proven with [[Parikh's theorem]] in 1961 by [[Rohit Jivanlal Parikh|Rohit Parikh]] in an MIT research report.<ref>{{cite book | last = Parikh | first = Rohit | title = Language-generating devices | publisher = Quarterly Progress Report, Research Laboratory of Electronics, MIT | date = January 1961}}</ref> 

The language <math>\{x | x=a^n b^m a^{n^{\prime}} b^m \text { or } x=a^n b^m a^n b^{m^{\prime}}, \text { where } n, n', m, m' \geq 1\}</math> is inherently ambiguous.<ref>{{Cite journal |last=Parikh |first=Rohit J. |date=1966-10-01 |title=On Context-Free Languages |journal=Journal of the ACM |volume=13 |issue=4 |pages=570–581 |doi=10.1145/321356.321364 |s2cid=12263468 |issn=0004-5411|doi-access=free }} Here: Theorem 3.</ref>

[[Ogden's lemma]]<ref>{{Cite journal |last=Ogden |first=William |date=Sep 1968 |title=A helpful result for proving inherent ambiguity |url=http://dx.doi.org/10.1007/bf01694004 |journal=Mathematical Systems Theory |volume=2 |issue=3 |pages=191–194 |doi=10.1007/bf01694004 |s2cid=13197551 |issn=0025-5661|url-access=subscription }}</ref> can be used to prove that certain context-free languages, such as <math>\{a^nb^mc^m | m, n \geq 1\} \cup \{a^mb^mc^n | m, n \geq 1\}</math>, are inherently ambiguous. See ''{{slink|Ogden's lemma#Inherent ambiguity}}'' for a proof.

The union of <math>\{a^n b^n c^m d^m \mid n, m > 0\}</math> with <math>\{a^n b^m c^m d^n \mid n, m > 0\}</math> is inherently ambiguous. This set is context-free, since the union of two context-free languages is always context-free. But {{harvtxt|Hopcroft|Ullman|1979}} give a proof that no context-free grammar for this union language can unambiguously parse strings of form <math>a^n b^n c^n d^n, (n > 0)</math>.{{sfn|Hopcroft | Ullman|1979|p=99-103|loc=Sect. 4.7}}

More examples, and a general review of techniques for proving inherent ambiguity of context-free languages, are found given by Bassino and Nicaud (2011).<ref>{{Cite web |author=Fredérique Bassino and Cyril Nicaud |date=December 16, 2011 |title=Philippe Flajolet & Analytic Combinatorics: Inherent Ambiguity of Context-Free Languages |url=https://algo.inria.fr/pfac/PFAC/Program_files/nicaud.pdf |url-status=live |archive-url=https://web.archive.org/web/20220925135141/http://algo.inria.fr/pfac/PFAC/Program_files/nicaud.pdf |archive-date=2022-09-25}}</ref>