7
$\begingroup$

For a language $L$, define: $$ NE(L) = \{x \in L : x \text{ is not the proper prefix of any string in } L\} $$

I'm trying to show context-free languages are not closed under this operation. I've been struggling for a long time now trying to find a counterexample, that is, a language $L$ such that $L$ is context-free but $NE(L)$ is not context-free, and have come up with nothing. I'd appreciate ideas or hints about languages to look into.

Edit: For the vast majority of context-free languages, it seems that either $NE(L) = L$ or $NE(L) = \varnothing$. I'm having trouble even finding candidate languages.

$\endgroup$
  • 1
    $\begingroup$ Let $L = \{a^n\} \cup \{a^nb^n\}$, then $NE(L) = \{a^nb^n\}$. But $NE(L) \neq L \wedge NE(L) \neq \varnothing$. $\endgroup$ – Anton Trunov Nov 18 '15 at 9:56
6
$\begingroup$

Rather than the language $L\subseteq \Sigma^*$ consider the language $L' =L\$\$$, so concatenate every string by two copies of $\$$ where $\$$ is a new symbol not in $\Sigma$.

Let $x\in \Sigma^*$. String $x\$$ is not a proper prefix of $L'$ iff $x\$\$ \notin L'$ iff $x\notin L$.

That should start you going.

$\endgroup$
  • 1
    $\begingroup$ I've been staring at this for a while now, and I'm just not seeing it. Firstly, $x\$$ is not even in $L'$, so it certainly cannot be in $NE(L')$ (which is a subset of $L'$). To apply the criterion "is not a proper prefix of $L'$", we need to start with an $x \in L'$, otherwise we're not getting information about $NE(L')$. Am I misunderstanding something here? $\endgroup$ – cemulate Nov 19 '15 at 0:19
  • 1
    $\begingroup$ You are right. To get around this I think it suffices to consider $L' = L\$\$ \cup \Sigma^*\$$ instead. $\endgroup$ – Hendrik Jan Nov 19 '15 at 2:19
  • 1
    $\begingroup$ Ah, clever. So essentially, we can use this construction to show that if $CFL$ were closed under $NE$, then it would have to be closed under complement to derive a contradiction. Alternatively, just pick a language whose complement fails to be CFL to get a counterexample. Thanks, I don't know when I would have thought of something like this... $\endgroup$ – cemulate Nov 19 '15 at 2:33
  • 1
    $\begingroup$ @AntonTrunov My suggestion for the "generic" case: The two parts of the language can be distinguished by their tails. So we can isolate $C(L)\$$ by intersecting with regular $\Sigma^*\$$. $\endgroup$ – Hendrik Jan Nov 19 '15 at 19:11
  • 1
    $\begingroup$ @AntonTrunov Sorry, I should have been more precise. Context-free languages are closed under intersection with regular languages. $\endgroup$ – Hendrik Jan Nov 19 '15 at 23:58

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.