3
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ See also here. $\endgroup$
    – Raphael
    Commented Mar 12, 2013 at 14:06

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Dec 20, 2012 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
    Commented Dec 20, 2012 at 13:32
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.