Re: Proof of inherent ambiguity?

dave_140390@hotmail.com (Dave Ohlsson) writes:


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


The standard example of a language with inherent ambiguity is


    L = L1 U L2, where
    L1 = {a^m b^m c^n | m,n>0}
    L2 = {a^m b^n c^n | m,n>0}


This is clearly context free, e.g. by the grammar


    S -> S1 | S2
    S1 -> A1 C
    S2 -> A B1
    A1 -> a b | a A1 b
    B1 -> b c | b B1 c
    C -> c | c C
    A -> a | a C


The intersection of L1 and L2 is {a^m b^m c^m | m>0}. Any string in
the intersection will, obviously, have two syntax trees by the above
grammar, but this does not prove inherent ambiguity.


However, {a^m b^m c^m | m>0} is not a context free language, so you
can argue that no context free grammar can decide which way to parse
strings in the intersection, so there will always be ambiguity. This
is not a stringent proof, but a formal proof can follow the same idea.


Torben

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