# 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 -> A | a | b
A -> aV | bT
V -> aV | bL
L -> aV
T -> bT | aM
M -> 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-> A | B
A -> aV | a
V -> aV | aVb | bVa
B -> bT | b
T -> 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 -> 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:

1. Break the language into two parts: $L_a = \{ w : \#_a(w) > \#_b(w) \}$ and $L_b = \{ w : \#_a(w) < \#_b(w) \}$. Below we concentrate on $L_a$.

2. Figure out a grammar for the language $L_= = \{ w : \#_a(w) = \#_b(w) \}$. Here the idea is that $L_= = (aL_=b + bL_=a)^*$.

3. Use the identity $L_a = L_=(aL_=)^+$ to construct a grammar for $L_a$.

• So basically I need to figure out the CFG of (a+b)* where # of a = b, then I use concatenation to put them all together? – LarsChung Nov 2 '13 at 7:12
• Well, here is a CFG for $(a+b)^*$: $S \to aS|bS|\epsilon$. Unfortunately, your exercise is more complicated. (Unless by $a,b$ you meant arbitrary expressions $\alpha,\beta$ rather than the symbols $a,b$.) – Yuval Filmus Nov 2 '13 at 7:15
• Unfortunately I am not able answer personal questions. If I remember correctly, MathType can export LaTeX, which you can use here (it is used in my answer). You can answer your question yourself with you suggested solution. – Yuval Filmus Nov 4 '13 at 6:33
• @LarsChung, I suggest you stop guessing and start trying to prove that your grammar works. Your last effort doesn't accept $aabbbbaa$. – Yuval Filmus Nov 4 '13 at 16:42
• I don't know how to $prove$ if my answers work, I can only test cases. Anyway, I've improved it as $S→aSb|bSa|abS|baS|Sab|Sba|SS|ϵ$. Even if I type google how to prove if CFG works, it doesn't give me anything – LarsChung Nov 5 '13 at 5:00

Remember that the following approach is also feasible:

1. Come up with a pushdown-automaton for the language.
2. Use the standard construction to get a grammar.

That's not a very insightful process (in terms of learning how to construct grammars) but it works.

• Yea, I know how to build a PDA with this language, but I have no idea how to convert it to CFG... – LarsChung Nov 4 '13 at 5:33
• @LarsChung Check the proof that PDA and CFG are equally powerful; it usually gives constructions in both directions. – Raphael Nov 4 '13 at 10:44

The unequal number of $$a$$'s and $$b$$'s have {equal number of $$a$$'s and $$b$$'s} with {{extra $$a$$'s } or {extra $$b$$'s}}

Extra $$a$$'s or extra $$b$$'s can be

• at the beginning
• at the end
• in between (ANY WHERE) and any number of times

Let $$P$$ derive strings with extra $$a$$'s

Let $$Q$$ derive strings with extra $$b$$'s

Let $$X$$ derive equal number of $$a$$'s and $$b$$'s

Let $$A$$ derive only $$a$$'s

Let $$B$$ derive only $$b$$'s

And $$S$$ derives the final language

\begin{align} &S\rightarrow P\mid Q\\ &P\rightarrow XAX\mid PP\\ &Q\rightarrow XBX\mid QQ\\ &X\rightarrow aXb\mid bXa\mid XX\mid \varepsilon\\ &A\rightarrow aA\mid a\\ &B\rightarrow bB\mid b \end{align}

\begin{align*} &S → U \mid V \\ &U → TaU \mid TaT \\ &V → TbV \mid TbT \\ &T → aTbT \mid bTaT \mid \epsilon \end{align*}

I hope it will predict a context-free grammar for the language consisting of all strings over $\{a,b\}$ containing an unequal number of a's and b's!

• This is identical to Vigneshwaran's answer from nearly a month ago, except that you use different non-terminals. And your answer is bad for exactly the same reasons theirs is: no explanation at all of why you think it is correct. – David Richerby Aug 26 '14 at 16:02

I know this is like a very old post, (and way past your homework deadlines), but here's the solution:

\qquad\begin{align*} L &\to L_a \mid L_b \\ L_a &\to L_=aL_a \mid L_=aL_= \\ L_b &\to L_=bL_b \mid L_=bL_= \\ L_= &\to aL_=bL_= \mid bL_=aL_= \mid \varepsilon \end{align*}

• How did you get there? Why is it correct? How can the OP or any other reader learn from this for the next task? – Raphael Jul 31 '14 at 17:08

\begin{align*} &S\to aB \mid bA \\ &A\to b \mid bS \mid aBB \mid \epsilon \\ &B\to a \mid aS \mid bAA \mid \epsilon \end{align*}

• Where did you get that from? Why is that grammar correct? What are the ideas behind it? We're not looking for one-line answers with no explanation; we're looking for answers that come with explanation, justification, etc. – D.W. Jul 31 '17 at 6:10
• FYI - this is wrong, "ab" is a match. – CeePlusPlus 4 hours ago