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

  • 2
    $\begingroup$ 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. $\endgroup$ – FrankW Jan 31 '14 at 16:30
  • $\begingroup$ would you please why it is no CF when |w1|=|w2|? $\endgroup$ – remo Jan 31 '14 at 16:35
  • 2
    $\begingroup$ @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. $\endgroup$ – FrankW Jan 31 '14 at 21:06
  • 1
    $\begingroup$ We still need a reference to the books and their precise statement. $\endgroup$ – Raphael Feb 1 '14 at 15:50
  • $\begingroup$ Unfortunately, the book is not in English. I will try to translate it if possible. Please wait $\endgroup$ – remo Feb 2 '14 at 3:38

Yes, the language is context-free.

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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