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.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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$.
answered Apr 11, 2019 at 12:03
-
-
1$\begingroup$ I'm afraid you'll have to take it from here. $\endgroup$ Commented Apr 11, 2019 at 12:20
$\begingroup$
$\endgroup$
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?
