HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Context-free languages not closed under making them "extension-free"

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#49627, answer score: 6

Revisions (0)

No revisions yet.