Define $\mathrm{Prefix} (L) = \{x\mid \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?


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 $xy\in 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.

  • $\begingroup$ Thank you for the answer. what do you mean by "You can start $T'_L$ on a string x", I still don't have a $T'_L$. If I have a $TM$ for $L$, which includes acceptpting state. Can I ,similar to automaton, just use the other states and when they reach to the end of the input "send" them to an accepting state? I hope you got what I mean. $\endgroup$ – Jozef May 9 '12 at 14:40
  • $\begingroup$ You are constructing $T^'_L$ using a copy of $T_L$. (Or, you may view it as augmenting $T_L$ to make it into $T^'_L$.) So you can assume $T^'_L$ starts with input $x$ on its tape (assuming that is how your TM model works) and then does some things, among them calling on the copy (or copies) of $T_L$. If $T_L$ in that scenario reaches an accepting state, you can use that to decide whether to accept with $T^'_L$. $\endgroup$ – David Lewis May 9 '12 at 20:31
  • $\begingroup$ Ok. I can use lots of copies of $T_L$ such that on every tape I'll put $xy$ where $y \in \sum^*$, and accept the word iff one of these machines has reached an accepting state, but the amount of these Turing machines can be infinite- how do I deal with that? Thanks! $\endgroup$ – Jozef May 10 '12 at 17:03
  • $\begingroup$ if I'm not mistaken, the other answer deals with that, no? $\endgroup$ – Jozef May 10 '12 at 18:11
  • $\begingroup$ It's not the infinity of the copies of $T_L$ that's the problem, as only finitely many will be active at any point, and as soon as one returns with a correct answer, you're done. It's more the fact that any of them might loop and never return, so you can't do them sequentially, one after the other. Two ways out are (a) non-deterministic branching, assuming your teacher has shown that; or (b) running the simulations "triangular round-robin" with a UTM: one step of each $T_L$, add a new $T_L$, repeat; when one accepts, you're done. BTW, (b) is how you prove non-determinism works in general. $\endgroup$ – David Lewis May 10 '12 at 22:39

Given $TM_L$ which acceps language $L$, let's construct $TM_{PL}$ to accept $Prefix(L)$.

Since the set of strings is countable, we can find an one-to-one mapping $f: N \to \Sigma^\star$ from natural numbers to all strings. So $TM_{PL}$ accepts $x$ iff there is an $i$ that $TM_L$ accepts $w(i) = x$ ## $f(i)$ (here ## means string concatenation). The intuitive idea to construct $TM_{PL}$ is to enumerate all $w(i)$ one by one and put $TM_L$ with input $w(i)$ to an universal turing machine $UTM$ to find whether $w(i) \in L$. But it fails to return the correct answer when $TM_{L}$ accepts $w(a)$ while it falls into an infinite loop in some $w(b)$ with $b < a$. Let's find how to avoid this situation.

Remember how to prove the conclusion that $N_+ \times N_+$ is countable, where $N_+$ is the set of all positive natural numbers. We can enumerate $(i, j)$ in the order $(1, 1) \to (2, 1) \to (1, 2) \to (3, 1) \to (2, 2) \to (1, 3) \ldots$. The same technique can be used to solve this problem, where pair $(i, j)$ means "Put $TM_L$ with input $w(i)$ to $UTM$ and find whether $TM_L$ accepts $w(i)$ in no greater than $j$ steps". The answer of each pair $(i, j)$ can be got in finite number of steps, and it's not hard to see that $x \in Prefix(L)$ iff there is a pair $(i, j)$ whose answer is yes.


RE means a TM generates the strings. Run that one, and each time there is some output, write its prefixes to the real output.

  • 1
    $\begingroup$ You should elaborate on that; if you compare yours to the other answers, you notice a lack of detail (and, arguably, effort). $\endgroup$ – Raphael Jan 18 '13 at 12:15
  • $\begingroup$ It was meant just as a pointer in the right direction. Building the relevant TMs is tedious, and adds nothing to understanding what is going on. $\endgroup$ – vonbrand Jan 18 '13 at 12:58
  • 1
    $\begingroup$ The question is old and there are already two upvoted answers here, one of which has been accepted. So the question stands as to why you think your pointer adds something new here, and why it is not "just" a comment (which I can concert it to). $\endgroup$ – Raphael Jan 18 '13 at 13:05
  • $\begingroup$ @Raphael: It feels simpler than the above. Just my opinion. $\endgroup$ – vonbrand Jan 18 '13 at 13:35
  • $\begingroup$ @vonbrand I agree that the method you suggest is actually simpler (and way more elegant! +1 for that). However your answer is somewhat cryptic: although an expert will be able to understand it, a non-expert will not be able to figure it out. Could you please explain your answer in greater details? $\endgroup$ – Ran G. Jan 19 '13 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.