0
$\begingroup$

$$S\rightarrow aAB$$ $$A\rightarrow bBb$$ $$B\rightarrow A|\epsilon$$

I'm choosing the string abbbb.

First left most derivation is the following:

$$S\Rightarrow aAB\Rightarrow abBbB\Rightarrow abebB\Rightarrow abebA\Rightarrow abebbBb\Rightarrow abebbeb = abbbb$$

Second left most derivation is the following:

$$S\Rightarrow aAB\Rightarrow abBbB\Rightarrow abAbB\Rightarrow abbBbbB\Rightarrow abbebbB\Rightarrow abbebbe = abbbb$$

Can someone tell me whether I'm correct in saying that the grammar is ambiguous?

This question has been taken from chapter 5 of "An Introduction to Formal Languages and Automata" by Peter Linz 5th Edition. The question states to prove that the grammar is unambiguous (however it is not). Hence, the aim of posting this question is to make sure that I've understood ambiguity and distinction between parse trees properly. I'm studying formal languages on my own and do not have the luxury of an instructor.

$\endgroup$
  • 1
    $\begingroup$ You are correct, but this does not prove the language is ambiguous. $\endgroup$ – reinierpost Oct 7 '16 at 22:06
  • $\begingroup$ @reinierpost Sorry, I meant is the grammar ambiguous? This is a question from Peter Linz automata book chapter 5 edition 5. They have asked to prove that the above "grammar" (not language) is unambiguous. However, it seems completely ambiguous to me. $\endgroup$ – aste123 Oct 8 '16 at 0:14
  • $\begingroup$ Do you have the definition of ambiguous grammar? What does it say? $\endgroup$ – Evil Oct 8 '16 at 0:25
  • 1
    $\begingroup$ @Evil The usual definition - having more than one parse trees or more than one left most derivation or more than one right most derivation for any string which is a member of the said grammar. $\endgroup$ – aste123 Oct 8 '16 at 1:10
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Oct 9 '16 at 11:20
3
$\begingroup$

Since you are trying to prove that the grammar is ambiguous, you must simply provide an example of a string where that grammar results in more than one parse tree or derivation. (Note that this is an entirely different ordeal than trying to prove that a grammar is unambiguous.) Since the string abbbb indeed has two distinct leftmost derivations, you have shown that the grammar is ambiguous. This proves that the grammar is not unambiguous since it is not the case that each string has at most one parse tree or derivation.

$\endgroup$

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.