Re: Proof of inherent ambiguity?

Rick Decker <rdecker@hamilton.edu>
25 Sep 2004 13:08:53 -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: Rick Decker <rdecker@hamilton.edu>
Newsgroups: comp.compilers,comp.theory,sci.lang
Date: 25 Sep 2004 13:08:53 -0400
Organization: Compilers Central
References: 04-09-137
Keywords: parse, theory
Posted-Date: 25 Sep 2004 13:08:53 EDT

Dave Ohlsson wrote:
> A context-free language is said to be inherently ambiguous if all the
> context-free grammars of that language are ambiguous.
>
> Now, I wonder how one can prove inherent ambiguity.
>
> Could anyone give an example of an inherently ambiguous context-free
> language AND the proof that that language is inherently ambiguous?


The canonical example is


{a^n b^n c^m d^m | n, m >= 0} \union {a^n b^m c^n d^m | n, m >= 0}


the proof is a bit tricky, but you shouldn't have trouble
finding references to it. I got 156,000 hits from Google on "inherent
ambiguity."




Regards,


Rick


Post a followup to this message

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