$L = \{ w : w \in \{a, b\}^* \land |w|_a = |w|_b\}$ where $|w|_a$ means number of $a$ in string $w$.

I came up with this grammar:

$S \rightarrow aSb \ |\ bSa \ | \ \epsilon .$

Can someone please tell me what is wrong with it?


1 Answer 1


Consider the string $w= abba $.
$w$ clearly belongs to $L$ as $|a|=|b|$ but there's no derivation which allows you to generate $w$ given your CFG.

In practice, your rules only deal with the imbalance in the number of $a$'s and $b$'s.
You need to make sure to generate every string $w \in (a+b)^*$ with the same number of $a$'s and $b$'s.

A CFG grammar for your language can be the following:

$S \rightarrow \epsilon\ |\ aSbS \ | \ bSaS $


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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