CS 254: Automata and Computability
Assignment #2
Due on paper by 8:30AM Wednesday, April 13.
Breaking news 4/13/11: Problem #7 below (i.e. #3 from p303) is cancelled. Also, we'll drop your
worst scoring problem, which frees you to skip one additional problem if you wish.
- Do problem 3 from page 301 (Homework 1) of Kozen
- Do problem 4 from page 316 (Miscellaneous Exercises) of Kozen
- Do problem 2 from page 302 (Homework 2) of Kozen
- Do problem 3 from page 302 (Homework 2) of Kozen
- Do problem 1 from page 303 (Homework 3) of Kozen
- Do problem 2 from page 303 (Homework 3) of Kozen
- Do problem 3 from page 303 (Homework 3) of Kozen
(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.
- Give a proof based on the closure properties of regular sets.
- 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.