4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 "end") - 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.

$\endgroup$
5
  • $\begingroup$ Thank you for your work, but I am confused. If $L$ is regular, then isn't $pref(L)$ regular too? Start with a DFA for $L$. When do we accept a string $x$ in $pref(L)$? if every continuation accepts, i.e., if we only find final states ahead. Note that is a property of the current state, not $x$ itself, so we can choose new final states to accept $pref(L)$ rather than $L$ using that automaton. $\endgroup$ – Hendrik Jan Oct 7 '20 at 1:08
  • $\begingroup$ I think i understand your confusion, but notice that pref(L) are all prefixes that have ALL of the possible continuations. This means, that such a DFA you describe would have to know wether all of those continuations exists beforehand. $\endgroup$ – nir shahar Oct 7 '20 at 7:54
  • $\begingroup$ Simply put, its not enough to know about specific continuations, but rather you need to know about all other possible continuations as well $\endgroup$ – nir shahar Oct 7 '20 at 7:59
  • $\begingroup$ In the case of a proper DFA all continuations exist, they might end up in some garbage state, but there is always exactly one next state for each symbol. $\endgroup$ – Hendrik Jan Oct 7 '20 at 15:34
  • $\begingroup$ It looks like I didnt understand what you meant (and I still dont). I would be glad for you to expand on your question so I will understand it better. $\endgroup$ – nir shahar Oct 8 '20 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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