Re: Proof of inherent ambiguity?

Nathan Sanders <nsanders@wso.williams.edu>
25 Sep 2004 11:29:45 -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: Nathan Sanders <nsanders@wso.williams.edu>
Newsgroups: comp.compilers,comp.theory,sci.lang
Date: 25 Sep 2004 11:29:45 -0400
Organization: Compilers Central
References: 04-09-137
Keywords: parse, theory
Posted-Date: 25 Sep 2004 11:29:45 EDT

  dave_140390@hotmail.com (Dave Ohlsson) wrote:


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


I think the following might be what you are looking for:


          L = {a^i b^j c^k | i=j or j=k}


Looking at strings like aabbcc, aaabbbccc, it seems that every grammar
must have at least two different parse trees, one for matching a's and
b's with arbitrary trailing c's, and one for matching b's and c's with
arbitrary preceding a's.


I'm not sure about a formal proof, though. I'm a bit rusty!


Nathan


--
Nathan Sanders
Linguistics Program nsanders@wso.williams.edu
Williams College http://wso.williams.edu/~nsanders
Williamstown, MA 01267

Post a followup to this message

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