1
$\begingroup$

I'm trying to work on this problem but I cant seem to find an approach to it:

For any language L ⊆ Σ∗ define the language PREFIX(L) := {w ∈ Σ∗ | some prefix of w is in L}

(a) Show that if L is decidable then PREFIX(L) is decidable.

(b) Show that if L is recognizable then PREFIX(L) is recognizable.

I understand the relationship among classes of languages (regular < context-free < decidable < Turing-recognizable) but I am still clueless on this. I also understand what decidable and recognizable means

$\endgroup$
0
$\begingroup$

Before we get started: A language L is Turing Recognizable if there exists a Turing Machine M such that, given as input a word w in L, can confirm that w belongs L in a finite number of steps. A language L is Turing Decidable if there exists a decider for it, i.e. a Turing Machine that, given any word w made up of characters from your alphabet, can tell you in a finite number of steps whether w is in L or not.

The key difference is that, even if a language L is recognizable, it might still be impossible given a word to determine whether it belongs to L or not in finite time, as the machine we have may never halt. On the other hand, if we had a decider for a language L, given enough time, it is always possible to determine whether a string belongs to L or not.

(a) If L is decidable, by definition, there exists a decider for it, i.e. a Turing Machine M1 that can always tell you in a finite number of steps whether a word w is in L or not. You should also know that any Turing Machine can simulate any other T.M. So what you need to do, in order to prove that PREFIX(L) is decidable, is to build a machine M2 that uses a simulator of M1 to decide PREFIX(L).

This is easily done as follows: M2 takes as input a word w, and simulates M1 on each prefix of w sequentially. This is a finite process since w is a finite word (and hence has a finite number of prefixes) and every simulation of M1 runs in finite time (since M1 is a decider). if at any point M1 accepts, then M2 accepts, otherwise, when all prefixes of w have been tried, M2 rejects.

(b)This kind of follows the same logic as the previous one: if L is Turing Recognizable then there exists a Turing Machine M1 that recognizes L.

Build M2 to recognize PREFIX(L) as follows: Given input w M2 simulates M1 on each prefix of w at the same time. If any of the simulations accepts then M2 accepts.

$\endgroup$

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.