How to eliminate context-free grammar's ambiguity

Question

I want to write a CFG that generates the words over {a,b} with the same number of ocurrences of a's and b's.

I have come up with a couple of possibilties so far. I think they're correct but they're all ambiguous, and I want the grammar to be non-ambiguous, this is one option:

S -> aX | bY | ε

X -> bS

Y -> aS

This is another one:

S -> aSb | bSa | SS | ε

And another one:

S -> aSb | bSa | abS | baS | ε

These grammars can generate the word ab in at least two different ways, for example, so they are ambiguous.

Is there any "tip" or "way" to eliminate ambiguity in a context free grammar such as this one?

Thanks for your time and have a nice day! :D

Answer 1

There is no general trick — indeed, given a context-free grammar, it is undecidable to determine whether it is ambiguous or not, and it is also undecidable to determine whether the language it generates is inherently ambiguous or not, see for example this answer on cstheory.

In your case, one way to go is to think of $a$ as corresponding to $\nearrow$ and of $b$ as corresponding to $\searrow$. We are interested in paths that start and end on the $x$ axis, for example $$ \begin{array}{cccccc} & \nearrow & \searrow \\ \nearrow & & & \searrow \\\hline & & & & \searrow & \nearrow \end{array} $$ We can decompose every such non-empty path into a first part, which ends the first time that the path reaches back to the $x$ axis, and the rest. If the first part starts with $\nearrow$, then it ends with a $\searrow$ and in between there is a path which never dips below where it started. We can denote such a path by $\top$. Any such path is either empty, or can be decomposed into a first part ending when the path reaches back to the initial level, followed by another $\top$ part. Putting everything together (and consider also the case in which the first part starts with $\searrow$), we obtain the following unambiguous context-free grammar (which for brevity is over $\nearrow,\searrow$): $$ \begin{align*} & S \to \epsilon \mid \color{red}\nearrow \top \color{red}\searrow S \mid \color{red}\searrow \bot \color{red}\nearrow S \\ & \top \to \epsilon \mid \color{red}\nearrow \top \color{red}\searrow \top \\ & \bot \to \epsilon \mid \color{red} \searrow \bot \color{red}\nearrow \bot \end{align*} $$