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!