A language that is not context free I working through some textbook exercises, and came across a problem that I'm struggling with.
Give a CFL $L$ such that $\{x|\forall y \in \Sigma^* \space xy \in L\}$ is not a CFL.
I've got the idea that we can let $L$ be formed by taking a language that is not CFL, and following each element by every string, and also add in the prefixes of elements of the non CFL language. But I'm not sure how to find a language such as this that is a CFL.
However, I'm struggling to think of an example with such a property.
Any help would be appreciated.
For simplicity, let us define that if $L$ is some language, $pref(L)$ to be the described language generated from $L$ (do not not to be confused with the language prefix operator)
Let us also define $\Sigma = \{a,b,c,e\}$.
We know that the language $L=\{a^nb^nc^n|n\in\mathbb N\}$ is not CFL, so we may want to use it.
Lets think in terms of your idea: we will want some other language $\hat L$ where $pref(\hat L)$ is similar to $L$ itself.
First, notice that simply applying your idea is not very useful: we may start with a word $aaabbbccc\in L$ and after we add to its the $y$ at the end, we can find ourselves with the word $aaabbbccccccccccccc\in \hat L$. This will make everything much harder to do, as this word could as well end up in $pref(\hat L)$ (think why!) and therefore in this case $pref(\hat L)$ is not very similar to $L$.
So how do we fix it? We can just add a new letter that will seperate our words in $L$ from the rest. This letter will be $e$ (short for &quot;end&quot;) - so our new definition for $L$ would be as follows: $L=\{a^nb^nc^ne|n\in\mathbb N\}$. Now, if we would have taken a look at $\hat L = L\Sigma^*$ (concatenation of those two languages) we would have $pref(\hat L)=\hat L$  but also $\hat L$ is very similar to $L$ in its core structure (and also is not a CFL for the same reason $L$ isn't).
Now we have a different problem, since $pref(\hat L)=\hat L$ we obviously can't have $\hat L$ being a CFL with $pref(\hat L)$ not a CFL. To fix this, we need a key observation: if we add some arbitrary word to $\hat L$, for example the word $ababa$ - then since it wasn't in $L$ already, it won't be in $pref(\hat L)$ too! (find a $y\in \Sigma^*$ where this word concatenation with $y$ is not in $\hat L$)
This means, we may somehow be able to add things to $\hat L$ while keeping $pref(\hat L)$ the same (and not a CFL). Adding all words of the form $we$ where $w\in\Sigma^*\setminus\{e\}$ with $|w|=3n$ for some $n\in\mathbb N$ should do the trick, but I will leave proving that $pref(\hat L)$ didnt change with those additions. Notice now that this language not is CFL, but its also regular! the automata that solves this language is simple: it checks whether the first occurrence of the letter $e$ is in a position that is a multiple of 3.
So finally, the language $\hat L=\{a^nb^nc^ne|n\in\mathbb N\}\Sigma^*\bigcup \{we|w\in\Sigma^*\setminus\{e\}\land \exists n\in\mathbb N .|w|=3n\}$ is regular (and hence a CFL) while $pref(\hat L)=\{a^nb^nc^ne|n\in\mathbb N\}\Sigma^*$ is not a CFL.

Sorry if this post was too long! I hope it helped you understand the problem and its solution on all of their steps and thinking methods.