Monday, 24 June 2013

Inherently ambiguous CFL's

A CFL that is inherently ambiguous is one for which no
  unambiguous CFG can exists.

          i i j j                  i j j i
     L= {a b c d  | i,j>0} union {a b c d  | i,j>0} is such a language

                       i i j j
  The productions for a b c d  could be
    1)  S -> I J
    2)  I -> a b
    3)  I -> a I b
    4)  J -> c d
    5)  J -> c J d

                       i j j i
  The productions for a b c d  could be (using K instead of J)
    6)  S -> a K d
    7)  S -> a S d
    8)  K -> b c
    9)  K -> b K c

  Now consider the case  i = j. This is a string generated by both
  grammars and thus will have two rightmost derivations.
  (one involving I and J, and one involving K)
  Thus ambiguous and not modifiable to make it unambiguous.

  An ambiguous grammar is a grammar for a language where at least one
  string in the language has two parse trees. This is equivalent to
  saying some string has more than one leftmost derivation or more
  than one rightmost derivation.

No comments:

Post a Comment