This is my attempt to solve an exercise from a formal languagues class.
Consider the following definition:
extend(L) = { w $\in$ $\Sigma^*$ | $\exists$ x $\in$ L, y$\in$ $\Sigma^*$ . w = xy }
In words: extend(L) is the set of all strings with some prefix in L;
1- Are CFLs (Context Free Languages) closed under 'extend'? ( If L is CFG, then extend(L) is also CFG?). Justify your answer.
Answer: Yes.
Let $G_L$ be the CFG gramar for L . We can construct a new $G_E$ for extend(L) as follows:
S' $\Rightarrow$ SE
E $\Rightarrow$ $a_1$E | $a_2$E | $a_n$E | $\epsilon$
(all other productions from $G_L$
where S' is the starting symbol for $G_E$; S is the starting symbol for $G_L$ > and $a_1$..$a_n$ are all the symbols from $\Sigma$
Is this correct?
2- Recursively Enumerable Languages are closed under 'extend' ?
Answer: False.
I feel like it is not RE because I can't create a TM for extend(L), but I don't know how to prove it. Reducing another well known undecidable problem to it, perhaps.... but how, and which one?
Thanks for any help!
The first part looks okay. For the second, though, $\mathrm{extend}(L)$ appears to be the concatenation of $L$ and $\Sigma^*$, and the r.e. languages are closed under concatenation. Consider a Turing machine $M$ that lists $L$. Modify it so that after listing the $n$-th word of $L$, it systematically lists all of the extensions of the first $n$ words by a maximum of $n$ letters.