Re: Proof of inherent ambiguity?

"Brian M. Scott" <b.scott@csuohio.edu>
25 Sep 2004 13:07:25 -0400

          From comp.compilers

Related articles
Proof of inherent ambiguity? dave_140390@hotmail.com (2004-09-24)
Re: Proof of inherent ambiguity? nsanders@wso.williams.edu (Nathan Sanders) (2004-09-25)
Re: Proof of inherent ambiguity? dido@imperium.ph (Rafael 'Dido' Sevilla) (2004-09-25)
Re: Proof of inherent ambiguity? torbenm@diku.dk (2004-09-25)
Re: Proof of inherent ambiguity? b.scott@csuohio.edu (Brian M. Scott) (2004-09-25)
Re: Proof of inherent ambiguity? rdecker@hamilton.edu (Rick Decker) (2004-09-25)
Re: Proof of inherent ambiguity? Michael.J.Fromberger@Dartmouth.EDU (Michael J. Fromberger) (2004-09-25)
Re: Proof of inherent ambiguity? hmessinger@comcast.net (Harlan Messinger) (2004-10-02)
| List of all articles for this month |

From: "Brian M. Scott" <b.scott@csuohio.edu>
Newsgroups: comp.compilers,comp.theory,sci.lang
Date: 25 Sep 2004 13:07:25 -0400
Organization: Compilers Central
References: 04-09-137
Keywords: parse, theory
Posted-Date: 25 Sep 2004 13:07:25 EDT

On 24 Sep 2004 00:26:52 -0400, Dave Ohlsson
<dave_140390@hotmail.com> wrote in sci.lang:


[...]


> Could anyone give an example of an inherently ambiguous context-free
> language AND the proof that that language is inherently ambiguous?


The language


{a^n b^n c^m d^m : n, m in N} U {a^m b^n c^n d^m : n, m in N}.


context-free and inherently ambiguous. The proof is long and
tedious and depends on the fact that there will always be two
different parse trees for some of the strings in the intersection
of the two pieces of the language. I believe that it can be
found in Hopcroft and Ullman, Introduction to Automata Theory.


Brian


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.