⟸ Go Back ⟸

Exercise 3 (Homework 5).

(R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, union, intersection, reverse)

\mathbf{R}, \mathbf{RE}, and \mathbf{coRE} are closed under union, intersection, and reverse

The goal of this exercise is to show some closure properties of \mathbf{R}, \mathbf{RE}, and \mathbf{coRE}.

Note

Recall that a class \cal C of languages is closed under a binary operation \circ (e.g., union or intersection) 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 reverse) if for any A \in {\cal C}, it holds that \circ A \in {\cal C}.

1. Union. Show the following properties:

   1. \mathbf{R} is closed under union.
   2. \mathbf{RE} is closed under union.
   3. \mathbf{coRE} is closed under union.

2. Intersection. Show the following properties:

   1. \mathbf{R} is closed under intersection.
   2. \mathbf{RE} is closed under intersection.
   3. \mathbf{coRE} is closed under intersection.

3. Set subtraction. Show the following property:

   1. \mathbf{R} is closed under set subtraction.

4. Reverse. Show the following properties:

   1. \mathbf{R} is closed under reverse.
   2. \mathbf{RE} is closed under reverse.
   3. \mathbf{coRE} is closed under reverse.