Assignment #3 consider the deterministic finite automaton M complete solution correct answer key

Assignment #3 consider the deterministic finite automaton M complete solution correct answer key

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.

n

(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: