$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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community$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?
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 $