6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – FrankW Mar 21 '14 at 21:32
  • 1
    $\begingroup$ 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? $\endgroup$ – Raphael Mar 21 '14 at 22:20
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.