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
$\begingroup$
$\endgroup$
1
-
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, 2014 at 9:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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.
$\begingroup$
$\endgroup$
It is quite simple, basically your CFG is ambiguous because of production $S\rightarrow aaB$. We can remove it but CFG must derive this means if we remove and CFG does not generate $aab$ then our approach will be waste so you just remove it and after removing you grammar will be like \begin{align} &S\rightarrow AB\\ &A\rightarrow a \mid Aa\\ &B\rightarrow b\\ \end{align} Now there is no ambiguity, you can check and suggest me if I'm wrong.
