Question

Turing Machine and Closure Operations

Show that Turing-decidable languages are closed under the following operations:

• union

• concatenation

• star

Answer 1

Answer :-

1.Union

Both decidable and Turing recognizable languages are closed under union.-

For decidable languages the proof is easy.

Suppose L1 and L2   are two decidable languages accepted by halting TMs   M1 and M2 respectively.

The machine for L1 ∪ L2 is designed as follows:

Given an inputx, simulate M1 on   x. If M1 accepts then   accept, else simulate   M2 on x.If M2   accepts then accept else reject.

Now suppose L1 and L2 are two Turing recognizable languages accepted by TMs   M1 and M2 respectively. Since L1 and L2 are Turing recognizable languages, therefore for strings that do not belong to these languages, the corresponding machines may not even halt.

The previous strategy will not work because we can have a scenario where M2   accepts x   but M1 loops forever.

the trick is to simulate both M1 and M2 “simultaneously”. In other words, we design a machine that executes one step of M1, followed by one step of M2, then again one step of M1and so on.

2.Concatenation

Let K and L be two turing recognizable languages ,and let M_K and M_L denote the turing machines that recognize K and L respectively.

We construct a non-deterministic turing machine M_KL that recognizes the language K_L.

i. Non-deterministically cut input w into w1 and w2

ii. Run M_K on w1. If it halts and rejects,reject.

iii. Run M_L on w2. If it accepts,accept. If it halts and rejects,reject .

Note the difference between the turing machines for recognizable and decidable languages.

Here, we need to take care of the fact that the machines M_K and M_L need not halt.

3.Star

For a turing recognizable language L , we construct a non-deterministic turing machine M_L∗ that recognizes L^∗.

The idea is similar to the decidable case.

i. On input w, non-deterministically cut w into parts w1 w2 ··· wn

ii. Run   M_L   on wi for all i. If M_L accepts all of them,accept. If M_L halts and rejects for any i, reject.

If there is a way to cut w into strings w1 w2 ··· wn such that each wi ∈ L,then there is a computation path in M_L∗ that accepts win a finite number of steps.