Given a language $L$ that is recursive prove that $Prefix(L) = \{ x \ | \ xv \in L\}$ is recursively enumerable.

My first attempt at this was to try and formulate an algorithm in pseudocode.

    for v in Σ*:
     w = xv
     if L-Decider(w) -> YES:
      return YES

Since $L$ is recursive a decider for it say $M$ exists and if $x$ is a prefix of $L$ at some point Prefix-Recogniser will respond with YES.

A Turing Machine can be easily implemented for the pseudocode above but is my thought process correct?


1 Answer 1


Yes your way is true. Because when L is recursive, your language should have a decidable alphabet. Because if it doesn't, then the set of your language's words can't contain a recursive subset. So your way to enumerate all possible words is true.


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.