patternMinor
Context-free grammar for language with unequal numbers of a and b
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)
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
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
$$\{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 -> aTThis 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 | bTaThis 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$.
-
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.