Problem Detail: Given following grammar: $$ begin{align} S rightarrow &A1B A rightarrow & 0A mid varepsilon B rightarrow & 0B mid 1B mid varepsilon end{align} $$ How can I show that this grammar is unambiguous? I need to find a grammar for the same language that is ambiguous, and demonstrate it. I know if I was asked to prove that the language is ambigious then I should find two different parse trees for same string, but I don’t know what to do.
Asked By : quartaela
Answered By : Hendrik Jan
To show a grammar is unambiguous you have to argue that for each string in the language there is only one derivation tree. In this particular case you can observe that $A$ only generates $0$’s, so the $1$ generated by the start symbol $S$ must be the first $1$ in the string. Any grammar can be made ambiguous by adding chain productions like $Sto S$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7518
