# Is the language of words with as many a's in the first as b's in the second part context-free?

Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language?

There is a book here that claims $L$ is not CF (without any elaboration), but I think we can construct a NPDA that accepts the language. My guess is we can construct the language with an NPDA where after reading some $a$ and $b$ and pushing $A$ for each $a$ into the stack, makes a guess to jump to a new state and consumes the pushed $A$ with each $b$.

• Your NPDA should work. So either the book is simply wrong, or you are misreading something (maybe the book is talking about a slightly different language, e.g. with the additional condition that $W_1$ and $W_2$ are of the same length). BTW: Note, that we usually say that an NPDA accepts a language, not that it constructs it. – FrankW Jan 31 '14 at 16:30
• would you please why it is no CF when |w1|=|w2|? – remo Jan 31 '14 at 16:35
• @remo Thinking about it more thoroughly, |w1|=|w2| is not sufficient to make the language non-context-free. But please edit the question as Raphael suggests, so we can properly solve your problem. – FrankW Jan 31 '14 at 21:06
• We still need a reference to the books and their precise statement. – Raphael Feb 1 '14 at 15:50
• Unfortunately, the book is not in English. I will try to translate it if possible. Please wait – remo Feb 2 '14 at 3:38

Let $w$ be a word in $\{a,b\}^*$. Decompose it as $w = u v$ where $|u| = N_b(w)$. \begin{align} N_a(u) &= N_a(w) - N_a(v) && \text{because $$w = u v$$} \\ &= N_a(w) - (|v| - N_b(v)) && \text{because $$v \in \{a,b\}^*$$} \\ &= N_a(w) - |w| + |u| + N_b(v) && \text{because $$|v| = |w| - |u|$$} \\ &= |u| - N_b(w) + N_b(v) = N_b(v) \\ \end{align} Thus we can decompose any word in the desired form: $L = \{a,b\}^*$. Constructing a PDA is left as an exercise to the reader.
This still works if the language contains other letters, by the way, but you have to take a prefix of $w$ that contains $N_b(w)$ letters in $\{a,b\}$ and arbitrarily many other letters.
Another way to see this is to notice that if there is an $a$ in $u$ and a $b$ in $v$, then you can swap the two letters, which results in a word that has the same balance $N_a(u) - N_b(v)$. $L$ is the set of words whose balance is zero for some split position. Iterate this decomposition until it becomes impossible: either $u$ contains no $a$ or $v$ contains no $b$. If we choose the split position so that $|u| = N_b(w)$ and $|v| = N_a(w)$, then now $u$ contains all the $b$'s and $v$ contains all the $a$'s: $N_a(u) = 0$ and $N_b(v) = 0$, and in particular the balance is 0.