Question

I am trying to prove the following:

Let $\Sigma $ be an alphabet not containing the symbol "$;$", and suppose that $L \subseteq \Sigma^*$; $\Sigma^*$ is recursively enumerable. If this is the case language $L' = \{x \in \Sigma^*: x; y \in L \ for \ some \ y \in \Sigma^*\}$ is recursively enumerable.

which left me a little bit confused. Since $";"$ is not in the alphabet $\Sigma$ should I seperate $x$ and $y$ and show that check for $x \in \Sigma^*$ and $y \in \Sigma^*$ is recursively enumerable?

Also, will this statement be the case if we checked for being recursive instead, that is if $L$ was recursive, is $L'$ necessarily recursive as well? And is the proof of this the same with the recursively enumerable case?

Any help will be appreciated.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top