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.

  • $\begingroup$ See also here. $\endgroup$ – Raphael Mar 12 '13 at 14:06

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 $S\to S$.

| cite | improve this answer | |
  • $\begingroup$ so if i search an unambiguity over a language i should check if there exists any chain production whatever it is ? and by the way thanks for your reply. $\endgroup$ – quartaela Dec 20 '12 at 12:38
  • 1
    $\begingroup$ For ambiguity you try to fiund one string with at least two parse trees (derivation trees). A chain production has the form $A\to A$. If such a production exists and $A$ occurs in the tree, you can find another tree by just adding $A\to A$. This will not change the word generated. And, no, it does not suffice to check for these productions. There might also be more general causes for ambiguity. $\endgroup$ – Hendrik Jan Dec 20 '12 at 13:32

This grammar is equivalent with $$ \begin{align} S \rightarrow &0A1B\mid 1B \\ A \rightarrow & 0A \mid \varepsilon \\ B \rightarrow & 0B \mid 1B \mid \varepsilon \\ \end{align} $$ and so like a simple grammar we can show that this grammar is not ambiguous. Of course this grammar is not simple.

| cite | improve this answer | |
  • $\begingroup$ What exactly is a »simple gramar«? Do you mean »regular grammar«? $\endgroup$ – FUZxxl Dec 23 '12 at 12:06
  • $\begingroup$ a grammar G is said to be simple, if all productions are of the form $$ A \rightarrow ax $$ where $A\in V, a\in T,x\in V^\ast$, and any pair $(A,a)$ occurs at most once in productions. $\endgroup$ – M.K. Dadsetani Dec 24 '12 at 10:07
  • $\begingroup$ Are the $\varepsilon$ productions allowed in simple grammars? $\endgroup$ – Hendrik Jan Dec 29 '12 at 0:42

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.