# Prove that context free languages aren't closed under DropMiddle

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.

• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – FrankW Mar 21 '14 at 21:32
• Are you sure that was the problem statement and not for DCFL? Anyway, this is not much more than a problem dump. What have you tried? Does $ww$ work? Why (not)? Which other non-context-free languages have you tried to use? – Raphael Mar 21 '14 at 22:20

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.