Re: Proof of inherent ambiguity?

torbenm@diku.dk (Torben Ęgidius Mogensen) wrote:


>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


Rather, A -> a | a A, correct?




--
Harlan Messinger

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