Question

Show that the collection of Turing-recognizable languages is closed under the operation of

1. union.
2. concatenation.
3. star.
4. intersection.
5. homomorphism.

Short answer

1. The collection of Turing recognizable language is closed under union operation.
2. The collection of Turing recognizable language is closed under concatenation operation.
3. The collection of Turing recognizable language is closed under star operation.
4. The collection of Turing recognizable language is closed under intersection operation.
5. The collection of Turing recognizable language is closed under homomorphism operation.

Step-by-step solution

Define Turing-recognizable languages.

The language recognized by a Turing machine is the string set that the machine accepts. A language is Turing recognizable if it is recognized by some Turing machine.

Thus a language is Turing recognizable, if some Turing machine accepts the string. However, a string that does not belong to the language may run forever.

Turing-recognizable languages are closed under the operation of a uniona)

Consider the two turing recognizable languages L₁ and L₂ that are defined by the turing machines M₁ and M₂ respectively. The union of the languages and the turing machines is represented as, L_L1L2 and M_L1L2 respectively.

On input s, run the languages L₁ and L₂ . It accepts or if both halt and reject, reject. Consider that the is a word from L_L1L2. M_L1L2 runs for the input string .as follows,

• Execute M₁ and M₂ on w separately.
• If any on the machine accepts, thenM_L1L2 accepts.
• If both machines reject, then either of M_L1L2 will loop.

Therefore, The collection of Turing recognizable language is closed under union operation

Turing-recognizable languages are closed under the operation of concatenation.b)

Consider the two turing recognizable languages L₁ and L₂ that are defined by the turing machines M₁ and M₂ respectively. The concatenation of the languages and the turing machines is represented as , L_L1L2 and M_L1L2 respectively.

On input s, run the languages L₁ and L₂ . It accepts or if both halt and reject, reject. Consider that the is a word from L_L1L2 . M_L1L2 runs for the input string .as follows,

• The string is divided into w₁ and w₂ non-deterministically.
• Execute M₁ on w₁ , if M₁ halts and rejects, reject.
• Execute M₂ on w₂ , if M₂ accepts, accept. If M₂ halts and rejects, reject.

Therefore, The collection of Turing recognizable language is closed under concatenation operation

Turing-recognizable languages are closed under the operation of a starc)

Use non-determinism to split up the stringin all possible ways$\omega ={\omega }_1{\omega }_2.......{\omega }_k$ and run machine M simultaneously on all parts. The new machine accepts if some of these computations accept.

Consider the turing recognizable language L₁ that are defined by the turing machine M₁. The star operation of the language and the turing machines is represented as , L₁^*.

On input s, run the languages L₁ as follows,

• Execute L₁ on w, it non-deterministically divided the string into
• Execute M₁^*on divided parts, if all the divided parts are accepted , accept, else reject.

Therefore, The collection of Turing recognizable language is closed under star operation

Turing-recognizable languages are closed under the operation of an intersection.d)

The machine is the same as in union. Turing machine which recognizes the union of languages L₂ and L₂ on input $\omega$ runs machines M₂ and M₂ simultaneously on a stringand accepts if any of these accept if any of these machines accept.

Consider the two turing recognizable languages L₂ and L₂ that are defined by the turing machines M₂ and M₂ respectively. The intersection of the languages and the turing machines is represented as , L_L1L2 and M_L1L2 respectively.

On input s, run the languages L₂ and L₂ Consider that thew is a word from L_L1L2 . M_L1L2 runs for the input string. as follows,

• Execute M₁ on w, if M₁ accepts, then M₂ on w, else reject.
• Execute M₂ on w₂ , if M₂ accepts, accept. If M₂ halts and rejects, reject.

Therefore, The collection of Turing recognizable language is closed under intersection operation

Turing-recognizable languages are closed under the operation of an Homomorphism.e)

Let $\mathit{f}\mathbf{:}\sum \to {\sum }^{*}$be homomorphism and L a Turning recognizable language, recognized by the machine M will be non-deterministic it first splits up input string in all possible ways such that $\omega ={\omega }_1{\omega }_2.......{\omega }_k$.

And for each of these splits, tries to find symbolsrole="math" localid="1663167165362" ${\alpha }_1,{\alpha }_2,{\alpha }_3,.......{\alpha }_k\sum$such that$f\left({\alpha }_n\right)={\omega }_n.$Then it runs machine input $u={\alpha }_1,{\alpha }_2,{\alpha }_3,.......{\alpha }_k\sum$. If any of these computations accept, then the machine M' accepts.

'Therefore, The collection of Turing recognizable language is closed under homomorphism operation.