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.
The blog provides study material for Computer Science(CS) aspirants. Mostly says "material nahi milta, padhun kahan se.", I think If you can not find content on the Internet, then you are not a CS student. Dedicated to (Prof. Rakesh Kumar, DCSA, K.U.Kurukshetra, HARYANA, INDIA)- "Ek teacher ka bahut jyada padhna, bahut jyada jaroori hota hai."
Monday, 24 June 2013
Inherently ambiguous CFL's
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment