# Ambiguous grammar to equivalent unambiguous grammar

I stumbled on this ambiguous grammar and I've been trying to make it unambiguous but it's still ambiguous.

Given the ambiguous CFG :
$$S \to A\mid B$$
$$A \to aAb\mid ab$$
$$B \to abB\mid \epsilon$$

My closet try was:

Given the ambiguous CFG :
$$S \to A$$
$$A \to aAb\mid C$$
$$B \to b$$
$$C \to abC\mid\epsilon$$

But the string "$$ab$$" is ambiguous

• What have you tried? Where did you get stuck? Here is a good series of questions to get you started: cs.stackexchange.com/questions/tagged/… – dkaeae Jan 17 '19 at 12:53
• In fact, the original CFG does not generate generate $aababb$, which is generated by your CFG as follows, $S\Rightarrow A\Rightarrow aAb\Rightarrow aCb\Rightarrow aabCb\Rightarrow aababCb\Rightarrow aababb$. – John L. Jan 17 '19 at 18:34
• Oh true, those that mean there isn't a solution to this? – Owonubi Job Sunday Jan 17 '19 at 19:00

As you have observed, the only problem in the original CFG is that the string $$ab$$ can be generated by both $$A$$ and $$B$$.
Here is a hint. Instead of generating $$ab, a^2b^2, a^3b^3,\cdots$$, can you let $$A$$ generate $$a^2b^2, a^3b^3,\cdots$$ without generating $$ab$$?
• @OwonubiJobSunday Instead of $A\to aAb\mid ab$, how about $A\to aAb\mid a^2b^2$? – John L. Jan 17 '19 at 16:41