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:

  1. Show that if L1 and L2 are decidable languages then so are:

    1. L1 UNION L2

    2. L1 INTERSECTION L2

    3. The COMPLEMENT OF L1, i.e. all strings in SIGMA* that are not in L1.

  2. Show that if L1 and L2 are Turing recognizable languages then so are:

    1. L1 UNION L2

    2. L1 INTERSECTION L2.

  3. Sipser's text page 148, problem 3.19

  4. Sipser's text page 168, problem 4.7

  5. Sipser's text page 168, problem 4.8

  6. (Bonus) Sipser's text page 149, problem 3.16. HINT: Make a separate argument in the case that the language is finite.

  7. (Bonus) Sipser's text page 170, problem 4.17.