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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ You are correct, but this does not prove the language is ambiguous. $\endgroup$
    – reinierpost
    Oct 7, 2016 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, 2016 at 0:14
  • $\begingroup$ Do you have the definition of ambiguous grammar? What does it say? $\endgroup$
    – Evil
    Oct 8, 2016 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, 2016 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, 2016 at 11:20

1 Answer 1

Reset to default
4
$\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.

Improve this answer
$\endgroup$

Your Answer

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

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