# How to show that given language is unambiguous

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.

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$.

• 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. Commented Dec 20, 2012 at 12:38
• 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. Commented Dec 20, 2012 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.

• What exactly is a »simple gramar«? Do you mean »regular grammar«?
– fuz
Commented Dec 23, 2012 at 12:06
• 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. Commented Dec 24, 2012 at 10:07
• Are the $\varepsilon$ productions allowed in simple grammars? Commented Dec 29, 2012 at 0:42