# CSEP 590TU Assignment #2

Autumn 2003

### Due: Wednesday, October 15, 2003.

Read chapter 4 of Sipser's text, Theorems 4.1 and 4.4 and section 4.2.

Problems:

- Show that if L
_{1} and L_{2} are decidable languages
then so are:
- L
_{1} UNION L_{2}
- L
_{1} INTERSECTION L_{2}
- The COMPLEMENT OF L
_{1}, i.e. all strings in SIGMA^{*}
that are not in L_{1}.

- Show that if L
_{1} and L_{2} are Turing recognizable
languages then so are:
- L
_{1} UNION L_{2}
- L
_{1} INTERSECTION L_{2}.

- Sipser's text page 148, problem 3.19
- Sipser's text page 168, problem 4.7
- Sipser's text page 168, problem 4.8
- (Bonus) Sipser's text page 149, problem 3.16. HINT: Make a separate
argument in the case that the language is finite.
- (Bonus) Sipser's text page 170, problem 4.17.