⟸ Go Back ⟸

Exercise 4 (Homework 5).

(R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, complement, concatenation, Kleene star, shift)

Other closure properties of \mathbf{R}, \mathbf{RE}, and \mathbf{coRE}

The goal of this exercise is to see how \mathbf{R}, \mathbf{RE}, and \mathbf{coRE} behave w.r.t. complementation, concatenation, Kleene star, and shift.

Note

Also recall that a class \cal C of languages is closed under a binary operation \circ (e.g., union or concatenation) if, for any A,B\in {\cal C}, it holds that A \circ B \in {\cal C}. Similarly, \cal C is closed under a unary operation \circ (e.g., complement or Kleene star) if for any A \in {\cal C}, it holds that \circ A \in {\cal C}.

1. Complement.

   1. Show that \mathbf{R} is closed under complement.
   2. Show that if A\in \mathbf{RE}, then \overline A\in \mathbf{coRE}.
   3. Show that if A\in \mathbf{coRE}, then \overline A\in \mathbf{RE}.

2. Concatenation.

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

3. Kleene star.

   1. Show that \mathbf{R} is closed under Kleen star.
   2. Show that \mathbf{RE} is closed under Kleen star.
   3. Is \mathbf{coRE} closed under Kleene star?

4. Shift (see Exercise 1.9).

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