Question

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

• union

• concatenation

• star

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

• union

• concatenation

• star

Each answer needs only be a short informal description of a Turing Machine (but it must still be sufficiently precise so someone could reconstruct a formal machine if needed).

Answer 1

SOLUTION-(1):- In this solution, we will show that Turing-decidable languages are closed under the following operations: union, concatenation, star

For Union operation :  Suppose that L₁ and L₂ are two decidable languages accepted by halting TMs M₁ and M₂ respectively. The machine for L₁ ∪ L₂can be designed as given below :
Given an input x, simulate M₁ on x. If M₁ will be accepted then accept, else simulate M₂ on x. If M₂ accepts then accept else reject.

For Concatenation operation : Let K, L be decidable languages. The concatenation operation of languages K and L is the language KL = {xy|x ∈ K and y ∈ L}. Because K and L are decidable languages, so it will follow that there exist turing machines M_K and M_L that decide the languages K and L respectively. In order to show that KL is decidable, a turing machine can be constructed that decides KL. This machine, M_KL can utilize the machines M_K and M_L to decide if a string is in KL or not. The machine can be constructed as given below:
Lets consider an input string w. We will be required to decide if w is of the form xy for x ∈ K and y ∈ L.If that is the scenario, there must be a place at which we can partition w into x and y. Because there exists only finitely multiple methods to partition the string, we can try all possibilities and accept if there is such a partition and reject otherwise. We will describe a nondeterministic turing machine because it is easier to describe.
(a) On input w, non-deterministically partition w into strings xy.
(b) Input x to M_K and y to y on M_L.
(c) accept if both M_K and M_L accept, else reject.
If there exists an accepting computation route, then we have found a successful split and the string is in KL. If all computation routes are reject, then the string is not in KL. In either scenario, it is convenient to see that the machine M_KL halts. Therefore, KL is decidable.

For Star operation : A language L, L^∗ = {x ∈ L∪LL∪LLL∪· · ·}. i.e. all strings obtained via concatenating L with itself, and so on. For showing that L^∗ is decidable, we require to find cuts of the input string w, such that each of them is accepted by the TM M_L that decides L. Suppose M_L^∗ be the machine that that decides L^∗ .
(a) On input w : For each way to cut w into parts w₁w₂ · · · w_n
(b) Run M_L on w_i  for i = 1, · · · , n.
(c) If M_L accepts each of the strings w_i accept.
(d) If all cuts have been tried without success, reject.

SOLUTION-(2):- In this solution, we will show that Turing-recognizable languages are closed under the following operations: union, concatenation, star

For Union operation : Suppose that L₁ and L₂ are two Turing-recognizable languages, and suppose M₁ and M₂ are TM_s that recognizes L₁ and L₂ respectively. We can construct a TM M that recognizes L₁ ∪ L₂ : On input w,
(a) Run M₁ and M₂ on w “in parallel”. That is, in each step, M executes one step of M₁ and one step of M₂.
(b) If either of M₁ and M₂ accepts, output ACCEPT. If both reject, output REJECT.
If M₁ or M₂ will accept w, then M will halt and accept w because M₁ and M₂ are executed in parallel and an accepting TM will halt and accept w in a finite number of steps. If both M₁ and M₂ will reject w, then M will reject w. If neither M₁ nor M₂ will accept w and one of them loops on w, then M will loop on w. Therefore, L(M) = L₁ ∪ L₂, and Turing-recognizable languages are closed under union.

For Concatenation operation :  Suppose that L₁ and L₂ are two Turing-recognizable languages, and let M₁ and M₂ be TMs that recognizes L₁ and L₂ respectively. We can construct a Nondeterministic TM N that recognizes L1 ◦ L2: On input w,
(a) Nondeterministically split w into two parts w = xy.
(b) Execute M₁ on x. If it rejects, halt output REJECT. If it accepts, go to Step (c).
(c) Execute M₂ on w. If it accepts, output ACCEPT. If it rejects, output REJECT.
If w ∈ L₁ ◦ L₂ , then there is a method to split w into two parts w = xy such that x ∈ L₁ and y ∈ L₂, therefore, M₁ will halt and accepts x, and M₂ will halt and accepts y. So, at least one branch of N will accept w. On the contrary, if w ∉ L₁ ◦ L₂, then for every possible splitting w = xy, x ∉ L₁ or y ∉ L₂ , so M₁ does not accept x or M₂ does not accept y. Therefore, all branches of N will reject w. So, L(N) = L₁ ◦ L₂ , and Turing-recognizable languages are closed under concatenation.

For Star operation : Let L be a Turing-recognizable languages, and let M be a TM that recognizes L. We can construct a TM M' that recognizes L^∗ : On input w,

(a) Nondeterministically select an integer k and split w into k parts w = w₁w₂ · · · w_k.
(b) Run M on each w_i . If M accepts all of w₁, . . . , w_k, output ACCEPT. If M rejects one of w₁, . . . , w_k, output REJECT.
If w ∈ L^∗ , then there exists a splitting of w = w₁w₂ . . . w_k so that w_i ∈ L for each i, and thus at least one branch of M' will accept w. On the contrary, if w ∉ L^∗ , then for every possible splitting w = w₁w₂ . . . w_k, w_i ∉ L for at least one i, therefore all branches of M' will reject w. So, L(M') = L^∗, and Turing-recognizable languages are closed under the star operation.

======================================================================