CS 254: Automata and Computability

Assignment #3

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

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. {aj bk | j + k = 10}
   4. {aj bk cn | j + k = n} (Note that for this problem, Σ = {a, b, c}.)
   5. {ap | p is prime}
   6. {x ∈ Σ* | #b(x) is odd and #a(x) is even}
   7. {x ∈ Σ* | x contains no substring equal to bab}
   8. {wwR | w ∈ Σ*} where wR is the reverse of the string w.
2. Do problem 15 from page 320 (Miscellaneous Exercises) of Kozen