patternMinor
Context-free languages not closed under making them "extension-free"
Viewed 0 times
freelanguagesclosedextensionunderthemcontextmakingnot
Problem
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.
$$
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#49627, answer score: 6
Revisions (0)
No revisions yet.