1
$\begingroup$

How can I prove that the following grammar is ambiguous:

$$ A \to AA\mid B \\ B \to aBb\mid ab $$

I tried finding a string that can be derived in two different ways, but to no avail.

$\endgroup$
1
$\begingroup$

The word $ababab$ can be derived in two different ways.

If you don't see why, I suggest starting with the simpler grammar $A \to AA|a$.

$\endgroup$
  • $\begingroup$ I dont get how you did that $\endgroup$ – Nnina Apr 11 at 12:19
  • 1
    $\begingroup$ I'm afraid you'll have to take it from here. $\endgroup$ – Yuval Filmus Apr 11 at 12:20
0
$\begingroup$

I could suggest a 6-letter word here but that would be too easy.

The productions for $B$ do not look promising. So check what can be done with $A$. Can you produce the same sequence of 3 non-terminals via 2 different derivations?

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