# Context-free languages not closed under making them “extension-free”

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.

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

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. • 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? – cemulate Nov 19 '15 at 0:19 • You are right. To get around this I think it suffices to consider L' = L\\ \cup \Sigma^*\$$ instead. – Hendrik Jan Nov 19 '15 at 2:19
• 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... – cemulate Nov 19 '15 at 2:33
• @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^*\$$. – Hendrik Jan Nov 19 '15 at 19:11