Ambiguous CFG to Unambiguous CFG Transformation

Question

I'm having a hard time converting this ambiguous CFG into an unambiguous one.

$S \rightarrow Sb \; \mid\; aaSb \;\mid \; b$

If I understood correctly, the language this CFG generates is composed of either:

• a single $b$, or
• at least two $b$'s preceded by an even number of $a$'s.

Can you help me disambiguate the CFG?

Answer 1

I think the following should do the trick.

$$S \rightarrow aaSb \mid X$$ $$X \rightarrow Xb \mid b$$

The idea is that once you pick $X$, you can no longer add $a$'s to the front, so the only way to produce $aabbb$ is $$S \rightarrow aaSb \rightarrow aaXb \rightarrow aaXbb \rightarrow aabbb$$