HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Proving that recursively enumerable languages are closed against taking prefixes

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
provingprefixeslanguagesareclosedrecursivelyagainstenumerablethattaking

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#1731, answer score: 3

Revisions (0)

No revisions yet.