5
$\begingroup$

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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented May 9, 2012 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
    Commented May 9, 2012 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
    Commented May 10, 2012 at 17:03
  • $\begingroup$ if I'm not mistaken, the other answer deals with that, no? $\endgroup$
    – Jozef
    Commented May 10, 2012 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
    Commented May 10, 2012 at 22:39
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
2
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • 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
    Commented Jan 18, 2013 at 12:15
  • 1
    $\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
    Commented Jan 18, 2013 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
    Commented Jan 18, 2013 at 13:05
  • $\begingroup$ @Raphael: It feels simpler than the above. Just my opinion. $\endgroup$
    – vonbrand
    Commented Jan 18, 2013 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.
    Commented Jan 19, 2013 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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