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$ 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$ 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$ 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$ 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$ Commented Dec 24, 2012 at 10:07
  • $\begingroup$ Are the $\varepsilon$ productions allowed in simple grammars? $\endgroup$ Commented Dec 29, 2012 at 0:42

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.