Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
The question is simple:
$\qquad \operatorname{DropMiddle}(L)=\{xy\in\Sigma^* \mid |x|=|y| \land \exists a\in\Sigma\colon xay\in L\}$.
Prove that CFL's aren't closed under $\operatorname{DropMiddle}$.
I should probably be looking for a counter example, but I'm coming up short. I know that the language $ww$ ($w$ is a word in some CFL) isn't a CFL, but I can't figure out if I'm on the right track at all.
First off, you are right about looking for a counter example. However, $ww$ is a dead end, since no matter what you add to the middle, you'll stiil have a language that is not context-free.
Hint 1: If the middle character is in some way special in $L$, you can essentially modify a PDA for $L$ to nondeterministically guess the middle and the removed letter and it will accept $\operatorname{DropMiddle}(L)$. So you should try to look for a language, where the dropping makes the middle special.
Hint 2: If the specialness of the middle is the only feature of $\operatorname{DropMiddle}(L)$, a PDA could just use its stack to determine the middle. So you need to force it to use the stack in a different way.
Solution:
$L = \{ aw_1aw_2aw_3a\ldots aw_na \mid w_i\in \{(,)\},~ w_1\ldots w_n \text{ is correctly parenthesized} \}$.
The $w_i$ part forces any PDA for $L$ or $\operatorname{DropMiddle}(L)$ to use its stack to count open parens. Thus it is impossible to check if, the single missing $a$ after dropping is indeed missing from the exact middle of the word.
Formally proving that $\operatorname{DropMiddle}(L)$ is not context-free should be doable with Ogden's Lemma.
Choose a word $(^k)^k(^k)^k$ (plus the $a$s inbetween) and mark $k$ characters each left and right of the middle.
Dropping the middle symbol is usually an action that is not observed. But we can make it special by using a special symbol.
Let $L = \{ a^n b^m \# a^n b^\ell \mid n,m,\ell \ge 0 \}$. Then $L$ is context-free.
Consider $K = \textrm{DropMiddle}(L) \cap a^*b^*a^*b^*$. The intersection with the regular language forces us to look at strings where $\#$ was indeed the middle symbol, i.e., strings where $m=\ell$. Thus $K = \{ a^n b^m a^n b^m \mid n,m \ge 0 \}$, which is not context-free.
