# How to eliminate context-free grammar's ambiguity

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

• 1) Your first grammar is regular, which can't be right (the language is not regular). 2) The second one can't generate abba. Also, rules of the form $S \to SS$ are poison for unambiguity. 3) In general deciding ambiguity is undecidable hence there's no easy algorithm to get rid of it. – Raphael Nov 19 '17 at 11:22
• Hint: you can use non-linear rules. For instance, there are simple unambiguous grammars for the Dyck language. – Raphael Nov 19 '17 at 11:26
• There is no a universal rule to eliminate ambiguity from a CFG. Each grammar may require a unique approach. For example, to git rid of ambiguity in the CFG for math expressions in a programming languages we introduce operator precedence: first unary operator, then mul and div, and then add and sub. – fade2black Nov 19 '17 at 11:43

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*}