Context-free grammar for language with unequal numbers of a and b I've been trying to get a CFG for the language of all words with unequal numbers of a and b, i.e.

$$\{u \in \{a, b\}^* \mid \text{number of occurrences of $a$ and $b$ in $u$ are unequal} \},$$

but it seems that I keep getting specific cases instead of the general case.

Here are some that I have tried:

(S being the start Variable)

S -&gt; A | a | b
A -&gt; aV | bT
V -&gt; aV | bL
L -&gt; aV
T -&gt; bT | aM
M -&gt; aT


This one's problem is that you can't create 2 of the same string if it's the lesser amount of alphabet.

So I've tried

S-&gt; A | B
A -&gt; aV | a
V -&gt; aV | aVb | bVa
B -&gt; bT | b
T -&gt; bT | aTb | bTa


This one also has problem because if you have a you need to have b on the opposite end.

Additionally, I know this is one of the huge problem in my process is that you start with 'a' or 'b' and use that as a flag for if there is more 'a' or there is more 'b'... 

I've been trying to think the way where you can input an alphabet (i.e S -&gt; aV | bV) so that I can start with any variable and I use cases or condition to go to different variable, but I end up with infinite variable situation.
Here are some hints:


Break the language into two parts: $L_a = \{ w : \#_a(w) &gt; \#_b(w) \}$ and $L_b = \{ w : \#_a(w) &lt; \#_b(w) \}$. Below we concentrate on $L_a$.
Figure out a grammar for the language $L_= = \{ w : \#_a(w) = \#_b(w) \}$. Here the idea is that $L_= = (aL_=b + bL_=a)^*$.
Use the identity $L_a = L_=(aL_=)^+$ to construct a grammar for $L_a$.