Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Problem $L = \{ w \in \{a, b\}^* : n(a) \neq 2 \cdot n(b)\}$

This can be done easily with NPDA, but I couldn't find a way to make it work with CFG. My idea was to break it into 2 cases: $n(a) > 2 \cdot n(b)$ or $n(a) < 2 \cdot n(b)$. I first try to generate a language which makes them equal, then add more $a$ or more $b$ but it couldn't handle many special cases. Here is what I got: $$ S \rightarrow U | V $$ $$ U \rightarrow TaU | TaT$$ $$ V \rightarrow TbV | TbT$$ $$ T \rightarrow TaTaTbT | TaTbTaT | TbTaTaT$$

$U$ generates $n(a) > 2 \cdot n(b)$, $V$ generates $n(a) < 2 \cdot n(b)$, and $T$ takes care of the equal case. Any idea would be greatly appreciated.

Update Following Hint by Brian
enter image description here

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Here’s a less general but more direct approach than mercio’s.

Your basic idea is fine, but as it stands, your grammar does not generate any terminal words: at the very least you need to expand that last production to

$$T\to TaTaTbT \mid TaTbTaT \mid TbTaTaT\mid\varepsilon\;.$$

Let $L'$ be the set of strings with exactly twice as many $a$’s as $b$’s. Think about the kind of string that should be generated by $U$, the ones with too many $a$’s. Every $b$ in such a word can be incorporated into a member of $L'$. Adjacent members of $L'$ can be concatenated into longer members of $L'$. If there’s more than one of these maximal members of $L'$, they must be separated by non-empty strings of $a$’s. There might also be strings of $a$’s at the beginning and end. Thus, the words generated by $U$ must have the form $a^*(L'a^+)^+L'a^*$. It would be convenient, therefore, to have a non-terminal $A$ that generates $a^*$, and another, $U_1$, that generates $(L'a^+)^+$. We might try something like this:

$$\begin{align*} &A\to Aa\mid \varepsilon\\ &U\to AU_1TA\\ &U_1\to U_1TaA\mid TaA \end{align*}$$

Certainly $A$ generates $a^*$, and $U_1$ generates $(L'a^+)^+$, so $U$ generates $a^*(L'a^+)^+L'a^*$. This may not be the most efficient solution, but it appears to work, and the same idea can be used to handle $V$.

share|improve this answer
    
I wonder how could you generate the string with less $a$? Because if you take $T$, it always generates at least 2 $a's$ each time. For example, string $bab$ should be ok. By the way, I forgot an empty string in my $T$, thanks for pointing that out. –  Chan Dec 11 '11 at 23:07
    
@Chan: All strings with an odd number of $a$’s are in $L$, and you can easily generate them separately. Then you can use the method above to generate the strings that have an even number of $a$’s but too many $b$’s. –  Brian M. Scott Dec 11 '11 at 23:25
    
I understand the idea, but the order of stacking more $b$ is really annoying. In fact, I was able to figure out the case $n(a) > 2n(b)$. But the other condition is a bit tricky, and again I ran into the situation that I have to break it up into many subcases. –  Chan Dec 11 '11 at 23:34
    
@Chan: $O\to BaBaBO\mid aB$ and $B\to Bb\mid b$ will get all strings with an odd number of $a$’s: you get $(b^*ab^*ab^*)^*ab^*$. –  Brian M. Scott Dec 11 '11 at 23:50
    
So is $O$ another special case besides $U$ and $V$? –  Chan Dec 12 '11 at 4:44

First, the following grammar produces the language $L_0$ containg words where $n(b) \neq n(a)$ $$S \rightarrow U \;|\; V $$ $$U \rightarrow TbT \;|\; TbU$$ $$V \rightarrow TaT \;|\; TaV$$ $$T \rightarrow bTaT \;|\; aTbT \;|\; \epsilon $$ It follows your idea of making two cases, and $T$ is the one giving words with equality and is the only non-obvious (but classic) one.

We have a map from $L$ to $L_0$ by transforming every $b$ into an $bb$. Let's try to pull this grammar back through this map. In order to do this, we need a grammar for the image of this map :

We introduce new symbols $U_b, V_b, T_b$ where $b U_b$ is intended to decompose into the words that $U$ can decompose into but beginning with an $b$. We do the same and have new symbols $U^b, V^b, T^b$ where $U^b b$ decomposes into the words $U$ can decompose into but ending with an $b$.

We get (you have to be careful when a $T$ appears because it can be empty) : $$ S \rightarrow U \;|\; V $$ $$ U \rightarrow (T^b b)bT \;|\; Tb(bT_b) \;|\; (T^b b)bU \;|\; Tb(bU_b) $$ $$ U_b \rightarrow (T_b^b b)bT \;|\; T_b b(bT_b) \;|\; T \;|\; (T_b^b b)bU \;|\; T_bb(bU_b) \;|\; U $$ $$ V \rightarrow TaT \;|\; TaV $$ $$ T \rightarrow b(bT_b)aT \;|\; a(T^bb)bT \;|\; aTb(bT_b) \;|\; \epsilon$$ $$ T_b \rightarrow TaT$$ $$ T^b \rightarrow b(bT_b)aT^b \;|\; a(T^bb)bT^b \;|\; aTb(bT_b^b) \;|\; aT$$ $$ T_b^b \rightarrow TaT^b$$ which describes the words of $L_0$ where every $b$ appears in a pair $bb$.

Now we can pull back and simplify the two symbols having only one rule and get this :

$$ S \rightarrow U \;|\; V $$ $$ U \rightarrow T^b bT \;|\; TbTaT \;|\; T^b bU \;|\; TbU_b $$ $$ U_b \rightarrow TaT^b bT \;|\; TaTbTaT \;|\; T \;|\; TaT^b bU \;|\; TaTbU_b \;|\; U $$ $$ V \rightarrow TaT \;|\; TaV $$ $$ T \rightarrow bTaTaT \;|\; aT^bbT \;|\; aTbTaT \;|\; \epsilon$$ $$ T^b \rightarrow bTaTaT^b \;|\; aT^bbT^b \;|\; aTbTaT^b \;|\; aT$$

Which should work, if I didn't mess up. Note that this method can be generalized to pulling back any grammar through any such map.

share|improve this answer
    
Your CFG accepts $aab$, but rejects $bab$. –  Chan Dec 11 '11 at 23:45
    
@Chan that's right. I think I should switch $a$ with $b$ everywhere. I removed words with 2n(a)=n(b) instead of the other way around. –  mercio Dec 12 '11 at 1:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.