Re: Proof of inherent ambiguity?

  dave_140390@hotmail.com (Dave Ohlsson) wrote:


> A context-free grammar is said to be ambiguous if at least one string
> in the context-free language defined by that grammar has more than one
> parse tree with that grammar.
>
> A context-free language is said to be inherently ambiguous if all the
> context-free grammars of that language are ambiguous.
>
> Now, I wonder how one can prove inherent ambiguity.
>
> Could anyone give an example of an inherently ambiguous context-free
> language AND the proof that that language is inherently ambiguous?


Others have given you some examples of languages which are inherently
ambiguous. More generally, you might also find the following result
interesting:


    W. G. Ogden, "A Helpful Result for Proving Inherent Ambiguity"
    in Mathematical Systems Theory, Vol. 2, #3 (1969), pp. 191--194.


The abstract reads:
    "It is shown that there is no `partial algorithm' (effective
    procedure that may fail to terminate) by which, given a context free
    grammar, one can always find an unambiguous context free grammar
    generating the same language if such an unambiguous grammar exists.
    The argument turns on the degree of unsovability of the inherent
    ambiguity problem for context free languages."


The paper is available from ACM:
    http://portal.acm.org/citation.cfm?id=800169.805417


Cheers,
-M
--
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA

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