Problem Detail: Define $mathrm{Prefix} (L) = {xmid exists y .xy in L }$. I’d love your help with proving that $mathsf{RE}$ languages are closed under $mathrm{Prefix}$. I know that recursively enumerable languages are formal languages for which there exists a Turing machine that will halt and accept when presented with any string in the language as input, but may either halt and reject or loop forever when presented with a string not in the language. Any help for how should I approach to this kind of a proof?
Asked By : Jozef
Answered By : David Lewis
Below is a hint for working with the Turing Machine (TM) formalism for RE languages. But finishing that approach from the hint depends on how you’ve been working with TMs. You have a TM, say $T_L$ to accept L and you want to construct a new TM $T_L^'$ for $text{Prefix}(L)$. You can start $T_L^'$ on a string $x$ and then do something to finish up with the hypothetical $y$ that completes $xyin L$. How you do that depends somewhat on the methods you have been using to work with TMs. But that’s a hint so far.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1731
