1. Consider the deterministic finite automaton M = ({q1, q2 , q3}, {0, 1}, δ, q1, {q2}) where δ is defined as follows:
δ(q1, 0) = q1 δ(q1, 1) = q2 δ(q2, 0) = q3 δ(q2, 1) = q2 δ(q3, 0) = q2 δ(q3, 1) = q2
Write an equivalent regular expression.
2. Prove that the following languages are not regular sets:
(a) L = {ai bj ck | i = 0 ∨ j = k, i, j, k ≥ 0}. Example strings include bccc, abbcc, aaa, etc.
(b) L = {ww | w ∈ {0, 1}
Example strings include 00, 11, 0101, 010010, etc.
(c) L = {a2
|n ≥ 0}. Example strings include aaaa, a16 , a64 , etc.
(d) L = {w | w ∈ {0, 1}∗, w is of the form (0i 1)n , for i = 1, 2, ..., n, n ≥ 0}. The strings of this language are ε, 01, 01001, 010010001, ...., each successive string of 0's being one larger than the previous.
3. Find the minimum state finite automaton for the language specified by the finite automaton
M = ({q0, q1, q2, q3}, {0, 1}, δ, q0, {q0 }) where δ is defined as follows: