Semidecidability/Decidability for strings seperated by a non alphabet symbol
-
04-11-2019 - |
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