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

  • 1
    $\begingroup$ What have you tried and where did you get stuck? have you checked out other questions about formal-grammars+ambiguity? $\endgroup$ – Raphael Oct 30 '14 at 9:41

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.

  • 1
    $\begingroup$ Actually, there is such a thing as an (inherently) ambiguous language, but you are correct, Rusty should be using the term 'grammar' instead of 'language'. $\endgroup$ – reinierpost Oct 30 '14 at 8:55
  • $\begingroup$ @reinierpost You are right of course. They are the languages for which no unambiguous grammar exists. But I didn't want to use too much terminology in the answer. $\endgroup$ – Hoopje Oct 30 '14 at 12:23
  • $\begingroup$ Well, it's been fixed now anyway. $\endgroup$ – reinierpost Oct 30 '14 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.