CS 254: Automata and Computability

Assignment #2

Due on paper by 8:30AM Wednesday, April 14.

1. Do problem 3 from page 301 (Homework 1) of Kozen
2. Do problem 1 from page 302 (Homework 2) of Kozen
3. Do problem 2 from page 302 (Homework 2) of Kozen
4. Do problem 1 from page 303 (Homework 3) of Kozen
5. Do problem 2 from page 303 (Homework 3) of Kozen

6. (Thanks to David Liben-Nowell) The symmetric difference A Δ B of two sets A ⊆ Σ* and B ⊆ Σ* consists of strings that are elements of either A or B, but not both. Formally, A Δ B = {x ∈ Σ* | x ∈ A iff x ∉ B} Your job for this exercise is to prove that if A and B are regular, then A Δ B is also regular.

   1. Give a proof based on the closure properties of regular sets.
   2. Give a proof by constructing a DFA. That is, given a DFA MA for which L(MA) = A and a DFA MB for which L(MB) = B, construct a DFA M for which L(M) = A Δ B.