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
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. $\endgroup$