Question

Prove that the class of decidable languages is not closed under homomorphism

Short answer

The class of decidable languages is not closed under homomorphism is proved.

Step-by-step solution

Step 1: Decidable languages.

Decidable languages are closed under complementation. To design a machine for the complement of a language, and simulate the machine for language on an input. If it accepts then accept and vice versa.

Decidable languages are closed under inverse homeomorphisms.

Step 2: Decidable languages is not closed under homomorphism.

a).

Consider the case where a language is recursive enumerable language. Design a Non Turing machine for $\mathrm{h}\left(\mathrm{L}\right),$as follows.

Suppose $\mathrm{w}$ is the input to $\mathrm{M}$. On a second tape, $\mathrm{M}$guesses some string $\mathrm{X}$ over the alphabet of $\left(\mathrm{L}\right)$, checks that $\mathrm{h}\left(\mathrm{x}\right)=\mathrm{w}$, and simulates the Turing machine for $\left(\mathrm{L}\right)$on $\mathrm{x}$, if so. If $x$is accepted, then $\mathrm{M}$accepts $w$.

so. If$\mathrm{x}$ is accepted, then $M$accepts$w$.

Also conclude that the recursive enumerable languages are closed under homomorphism. However, the recursive languages are not closed under homomorphism. To see why, consider the particular language$\left(\mathrm{L}\right)$consisting of strings of the form$(\mathrm{M},\mathrm{w},\mathrm{ci}),$ where$\mathrm{M}$a coded Turing machine with binary input alphabet is $\mathrm{w}$, is a binary string, and c is a symbol not appearing elsewhere. The string is in$\left(\mathrm{L}\right)$if and only if$\mathrm{M}$accepts w after making at most moves.

As defined this particular language to break the closure of recursive language.

First let’s check that indeed $\left(\mathrm{L}\right)$is recursive. Well, yes it is, because to see whether a string is in the language, we have to simulate M on w for at most i move.

So stop the machine after$\mathrm{i}+1$moves and know for sure you should reject.

However, if we apply to$\left(\mathrm{L}\right)$the homomorphism that maps the symbols other than c to themselves, and maps$\mathrm{c}\mathrm{to}\mathrm{\epsilon }$, we find that$h\left(L\right),$is the universal language, which we called Lu. We know that$\left(L\right)$ is not recursive. So in three words, $\left(L\right)$is recursive, $h\left(L\right),$= Lu is Recursive enumerable but not recursive. So recursive languages are not closes under homomorphism.

Another version to show that recursive languages are not closed under homomorphism. Consider a Turing Machine M, whose language is Recursive enumerable. Now consider the language defined as the sequence of computation the Turing machine does when it accepts a string. Actually, put hats on the first ID. So here,

$\mathrm{l}=\mathrm{q}0\mathrm{x}ˆ1\mathrm{x}ˆ2...\mathrm{x}ˆ\mathrm{n}\text{'}\mathrm{x}01\mathrm{a}1\mathrm{x}2...\mathrm{xn}\text{'}...$

Where,$\mathrm{w}=\mathrm{x}1\mathrm{x}2...\mathrm{xn}$ is the input.

The language is clearly recursive.

Now, just check whether the transitions respect the transitions or Consider the homomorphism that maps hated symbols to their version without hats, and everything else, including ', to ε.

Clearly, $\mathrm{h}\left(\mathrm{l}\right)=\mathrm{w}.\mathrm{Soh}\left(\mathrm{L}0\right)=\mathrm{L}$.

In other words, a homomorphism between a recursive.

Hence, the class of decidable languages is not closed under homomorphism is proved.