HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Context-free grammar for language with unequal numbers of a and b

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
freewithnumbersandlanguagegrammarforcontextunequal

Problem

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.

Solution

Here are some hints:

-
Break the language into two parts: $L_a = \{ w : \#_a(w) > \#_b(w) \}$ and $L_b = \{ w : \#_a(w)

-
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$.

Context

StackExchange Computer Science Q#16642, answer score: 9

Revisions (0)

No revisions yet.