Re: Proof of inherent ambiguity?

From: Brian M. Scott (b.scott_at_csuohio.edu)
Date: 09/25/04 

Date: 25 Sep 2004 13:07:25 -0400

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

Relevant Pages

  • Re: Is Python context-sensitive?
    ... I've recently participated in a discussion of whether Python programming ... language is context-sensitive or context-free. ... contains just indentation and an "a" symbol. ...
    (comp.theory)
  • Re: Is Python context-sensitive?
    ... context-free or do we have to take lexer into consideration as well? ... but solely about whether the syntax of the language can ... using a FSA with a stack? ... apply to programming languages used in practise. ...
    (comp.theory)
  • Re: Proof of inherent ambiguity?
    ... > in the context-free language defined by that grammar has more than one ... > parse tree with that grammar. ... I wonder how one can prove inherent ambiguity. ...
    (comp.theory)
  • Re: Proof of inherent ambiguity?
    ... > in the context-free language defined by that grammar has more than one ... > parse tree with that grammar. ... I wonder how one can prove inherent ambiguity. ...
    (sci.lang)
  • Re: history of generative grammars
    ... In automata theory, the hardware state under free input ... is taken as a language, and you ask whether something is in the language, ... It's not context-free. ...
    (comp.theory)