Skip to main content
3 of 4
title, formatting, language; removes superfluous "no homework" assertions
Raphael
  • 72.9k
  • 30
  • 181
  • 393

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.

remo
  • 141
  • 3