CS 254: Automata and Computability

Assignment #3

Due on paper by 8:30AM Friday, April 23.

1. For this problem, let Σ = {a, b} unless instructed otherwise. For each of the following sets, say whether it is regular or non-regular, and provide a proof of your answer. Your proofs may use any of the tools we have discussed so far--construction of a DFA, NFA, or NFA-ε, use of closure properties, construction of a regular expression, the pumping lemma, etc.

   1. {aj bk | j ≥ 0, k ≥ 0}
   2. {aj bk | j ≥ 0, k ≥ 0, j < k}
   3. {an2 | n ≥ 0}
   4. {x ∈ Σ* | #b(x) is even and #a(x) is odd}
   5. {x ∈ Σ* | x contains no substring equal to abbaa}
   6. {ww | w ∈ Σ*}
   7. {x ∈ {0,1}* | x represents a binary integer n such that n mod 3 = 1 or 2}
2. Do problem 13 from page 320 (Miscellaneous Exercises) of Kozen
3. Do problem 15 from page 320 (Miscellaneous Exercises) of Kozen
4. Do problem 29 from page 323 (Miscellaneous Exercises) of Kozen
5. Do problem 30 from page 323 (Miscellaneous Exercises) of Kozen [Both parts of this one are very hard.]