Re: Proof of inherent ambiguity?

From: Harlan Messinger (hmessinger_at_comcast.net)
Date: 10/02/04

  • Next message: Tim Peters: "Re: Another set with cardinality |Z|" 
    Date: 2 Oct 2004 01:11:29 -0400

    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
  • Next message: Tim Peters: "Re: Another set with cardinality |Z|"
    • Quantcast