[SOLVED] Comp 335 – introduction to theoretical computer science 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
q33. [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}.