2
$\begingroup$

There is a grammar G given:

    S->XaX
    X->aX|bX|eps

I just replied to the first question that was about showing that this grammar is ambiguous. The second question is to find an unambiguous equivalent grammar of this grammar given. I don't really know how to do it or from where to start. Can anyone help me?

$\endgroup$
1
$\begingroup$

Your language consists of all words over $\{a,b\}$ which contain $a$. This is a regular language, and so it has an unambiguous regular grammar - essentially a DFA - which is not so difficult to construct for this language. Regular grammars constructed from DFAs are unambiguous, so this would be an unambiguous grammar for the same language.

$\endgroup$

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.