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
Best Answer
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.