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.

Improve this question
$\endgroup$
1
  • 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, 2015 at 9:56

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
8
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.