Context free grammar for language $\{ \{a,b\}^*$: where the number of $a$'s is unequal to the number of $b$'s$\}$

86 Views Asked by At

I've seen many solutions for when the number of $a$'s and $b$'s ARE equal but how should the grammar be for the time when the numbers are unequal?

So far I have this but it can't produce many things like aba:

S -> A | B
A -> aAb | bAa | aA | a
B -> aBb | bBa | bB | b
1

There are 1 best solutions below

0
On BEST ANSWER

You can't produce aba because you just forgot some rules, consider this corrected version:

S -> A | B
A -> aAb | bAa | abA | baA | Aab | Aba | aA | Aa | a
B -> aBb | bBa | abB | baB | Bab | Bba | bB | Bb | b