I need to find the production rules for the following language:

$L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$

Well, the first thing I could come up with is

$S \to aSb | \epsilon$

But this only covers the situation where all symbols $a$ precede $b$.So I tried to add all rules containing only one symbol of $a$, $b$, and one non-terminal symbol on the right-side:

$S \to aSb|bSa|abS|baS|Sab|Sba|\epsilon$

Do you think this would work?

I used this website CFG Developer and entered my productions, and for the string "bbbbaaaaabababbabababbaa" the output is false, meaning that the string cannot be produced by the mentioned rules.

Does anyone know where the mistake is?


1 Answer 1


By your above mentioned grammar $S \to aSb|bSa|abS|baS|Sab|Sba|\epsilon$ has four redundants $abS,baS,Sab,Sba$ and one missing term is $SS.$ Because if you use $S \to aSb|bSa|\epsilon$ only after removing redundants then the strings that does starts and ends with same symbol like $abba$ is not possible to generate(but $n_a(w)=n_b(w)$), that's why you need to add $SS.$

Therefore your complete grammar is $S \to aSb|bSa|SS|\epsilon$


Not the answer you're looking for? Browse other questions tagged or ask your own question.