SOLVED COMP 335 Assignment 2

1. [20 Points] For each of the following languages over the alphabet Σ = {a, b} give an NFA (as a transition diagram) with the specified number of states. Hint: try simplifying a DFA and/or use λ transitions. (a) The language {a n : n ≥ 0} ∪ {b na : n ≥ 1} with at most 4 states. (b) The language {w : w either has no consecutive a’s or no consecutive b’s} with at most 5 states. (c) The language {w : w contains an even number of a’s or exactly two b’s} with at most 6 states. (d) The language {ab, aab, aba} ∗ with at most 4 states. 2. [20 Points] Let Σ = {a, b}. Convert each NFA below to a DFA using the subset construction. Draw the transition diagram of your DFA, label the states of your DFA by subsets of states of the original NFA. (a) a a b b λ λ q0 q1 q2 q3 q4 (b) a, b a, b a b b a q0 q1 q2 q3 3. [20 Points] Find a regular expression for each of the following languages. (a) {ban b m : n ≥ 3, m ≥ 2}. (b) {w ∈ {a, b} ∗ : every maximal substring of w consisting entirely of symbols a is of length exactly 3}. (c) {w ∈ {a, b} ∗ : w does not contain bab as a substring}. (d) {w ∈ {a, b} ∗ : w begins with bb and nb(w) mod 3 = 0}.