Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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) |
| 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
Return to the
comp.compilers page.
Search the
comp.compilers archives again.