Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
See also here. –  Raphael Mar 12 '13 at 14:06
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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. –  quartaela Dec 20 '12 at 12:38
1  
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. –  Hendrik Jan Dec 20 '12 at 13:32
add comment

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.

share|improve this answer
    
What exactly is a »simple gramar«? Do you mean »regular grammar«? –  FUZxxl Dec 23 '12 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. –  M.K. Dadsetani Dec 24 '12 at 10:07
    
Are the $\varepsilon$ productions allowed in simple grammars? –  Hendrik Jan Dec 29 '12 at 0:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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