Question

Show that the collection of decidable languages is closed under the operation of

a. union.

b. concatenation.

c. star.

d. complementation.

e. intersection.

Short answer

a) The decidable languages are closed under the operation of union.

b)The decidable languages are closed under the operation of the concatenation.

c) The decidable languages are closed under the operation of the star.

d) The decidable languages are closed under the operation of thecomplementation.

e) The decidable languages are closed under the operation of the intersection.

Step-by-step solution

Define decidable languages.

A Turning machine that halts and never goes to the infinite loop is called deciders. They always halt and decide whether to accept or reject the input. It always halts in accept or reject states.

A language of Turing machine L(M)if there is turning machine M, which decides a languages L and M halts on every input, such that.

L(M)=L

A decider of languages is the one that decides the language. It is also called Recursive languages. So, the decidable languages always solve the decision problem.

Prove that the decidable languages are closed under the operation of the union

(a)

Assume two Turing machines M₁ and M₂ that are non-deterministic. Also, assume two languages L₁ and L₂ that are accepted by the turing machine.

The Turing machine M₁ and M₂ perceives the languages L₁ and L₂ .

To show that NL is closed under operation union, proceed as follows.

$L_1=L_1\cup L_2$ …… (1)

The first non-deterministic bit is used to create machines for in (1).

Therefore, the decidable language is closed under operation Union.

Prove that the decidable languages are closed under the operation of the concatenation.

(b)

Assume that we have two Turing machines M₁ and M₂ that are non-deterministic. Also assume the two languages L₁ and L₂ where,

$L_{1}and{L}_2\in NL$

The Turing machines M₁ and M₂ perceives the languages L₁ andL₂ in log space.

to show that NL is closed Under operation concatenation we will proceed as follows.

L = L₁ . L₂ ……(2)

The first non-deterministic bit is used to create machines for in (2).

Therefore, the decidable language is closed under concatenation.

The decidable languages are closed under the operation of the star.

(c)

Assume that we have two Turing machines M₁ and M₂ that are non-deterministic. Also assume the two languages L₁ and L₂ where,

$L_{1}and{L}_2\in NL.$

The Turing machines decide the languages L in log space.

The NL is closed under the operation use Turing machines as follows:

1. A word is taken which can be broken into sub-words w₁ , w₂ ,.......w_n the word such that for any length all sub-words of w are in L.
2. The word is inL if$Lw\in {\sum }^n$
   Thus, L* is accepted by the machine.

After L* is accepted by the machines, the length of the first sub-word w₁ is figured out by the machines using the non-determinism technique and they recreate M on it the length of the word w₁ is figured out by the machine. Thus even if the machines M attempts to move the input reading ahead of this length the machine M should be mimicked in such a way that the information taps will contain just w₁

1. The machine will reject it w₁ is rejected by the machine M.
2. If w₁ is accepted by the machine then our machines will also accept it. The machine will now

Check the input of w₁. If machines cannot verify the inputs of w₁ then it will continue to string w₂.

The branch will continue till it dismissed or when the entirety of the input word is surrounded by acknowledged sub-word in which case we acknowledge it.

Thus NL is closed under the operations star

$L*\in NL$.

Therefore, The decidable languages are closed under the operation of the star.

The decidable languages are closed under the operation of the complementation

(d)

Decidable languages are closed under complement. If a language is a decidable there is a TM that accepts and halts string that belong to the language and rejects and halts string that did not belong to the language. Flipping the accepted and reject states generates a TM to decide the complement of these languages.

Not all recognizable languages are closed under complement if the complement of a recognizable language is also recognizable, the language, in fact, is decidable.

Suppose L is recognizable and M recognizes L. Assume that the complement L is also recognizable N recognizes L.

On input w for $i=0,1,2,K$

1. Run M on w for i steps. If M accepts, accept.

2.Run N on w for i steps. If N accepts, reject.

Therefore, if a language and its complement is recognizable. Then the language is decidable.

Prove that the decidable languages are closed under the operation of the intersection.

(e)

Both decidable and Turing recognizable languages are closed under intersection. Run the turing machineof both the languages on the given accept if and only if both the machines. In the case intersection can run the TM of L₁ and L₂ one after the other (as opposed to union).

Therefore, The decidable languages are closed under the operation of the intersection.