Show that the class of Turingdecidable languages is closed u

Show that the class of Turing-decidable languages is closed under the operation of (a) complementation (b) concatenation

Solution

a)- The class of decidable languages is closed under complement.

Proof:

Considered M be a turing machine defined on language A.Now we have to construct a TM M that decides A in the following way: M = “On input value suppose w:

1. Simulate M on w.

2. Accept it if M rejects, reject if M accepts”.

NOTE: for decidability we always have to check two things – M always halts, and M gives the correct result on every input. M always halts because M always halts. M gives the correct result, because if w A, M will accept, and so M will reject, and if w / A, M will reject, in which case M will accept.

b)- The class of decidable languages is closed under concatenation.

Proof:

Let A and B be decidable languages. The concatenation of languages A and B is the language AB = {xy|x A and y B}. Since A and B are decidable languages, it follows that there exist turing machines MA and MB that represent the language A and B respectively. In order to prove that AB decidable, we can construct a turing machine that decides AB.

This machine, MAB can use the machines MA and MB to decide if a string is in KA or not. The machine can be constructed as follows : Consider an input string p. We need to decide if p is of the form xy for x A and y B. If this is the case, there must be a position at which we can partition p into x and y. Since there are only nitely many ways 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 since it is easier to describe. i. On input p, non-deterministically partition p into strings xy. ii. Input x to MA and y to y on MB. iii. accept if both MA and MB accept, else reject. If there is an accepting computation path, then we have found a successful split and the string is in AB. If all computation paths reject, then the string is not in AB. In either case, it is easy to see that the machine MAB halts. Thus, AB is decidable.