⟸ Go Back ⟸

Exercise 5 (Homework 5).

(R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, homomorphism, inverse homomorphism)

\mathbf{R}, \mathbf{RE}, and \mathbf{coRE} and homomorphisms

The goal of this exercise is to investigate how \mathbf{R}, \mathbf{RE}, and \mathbf{coRE} behave under homomorphisms and inverse homomorphisms.

Note

Also recall that a class \cal C of languages is closed under homomorphism if for any A \in {\cal C} and homomorphism \sigma, \sigma(A) \in {\cal C}. Also, {\cal C} is closed under inverse homomorphism if for any A \in {\cal C} and homomorphism \sigma, \sigma^{-1}(A) \in {\cal C}.

1. Homomorphism.

   1. Show that \mathbf{R} is not closed under homomorphism.
   2. Show that \mathbf{RE} is closed under homomorphism.
   3. Is \mathbf{coRE} closed under homomorphism?

2. Inverse homomorphism.

   1. Show that \mathbf{R} is closed under inverse homomorphism.
   2. Show that \mathbf{RE} is closed under inverse homomorphism.
   3. Is \mathbf{coRE} closed under inverse homomorhpism?