I'm wondering if somebody can please help me to understand how I go about converting this grammar to an unambiguous grammar. If you can point me in the right direction, I would greatly appreciate it.
S -> AB | aaB
A -> a | Aa
B -> b
Asked By : Rusty
Answered By : Hoopje
First, there is a difference between a language and a grammar. A language is just a set of strings, while a grammar is a way to specify such languages. The attribute "ambiguous" applies to grammars. There is no such thing as a "unambiguous language". What you want is an unambiguous grammar for the same language.
In general, it is not possible to give an unambiguous grammar for an arbitrary ambiguous grammar, because there exist (context free) languages for which no unambiguous grammar exists.
In your case, however, an unambiguous grammar does exist. To find it, you have to analyse the grammar. What string are generated by the variable B? What strings are generated by the variable A? So, what strings can be derived from AB and what strings from aaB? From the answer to this last question you will see how the grammar can be simplified without changing the language it generates.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/32470
0 comments:
Post a Comment
Let us know your responses and feedback