ASSIGNMENT 3 Consider the deterministic finite automaton M 2

Question: #75

ASSIGNMENT #3

1. Consider the deterministic finite automaton M = ({q1, q2, q3}, {0, 1}, ∂, q1, {q2}) where is
dened 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 = faibjck j i = 0 _ j = k, i; j; k 0g. Example strings include bccc, abbcc, aaa, etc.
(b) L = fww j w 2 f0; 1g+g. Example strings include 00, 11, 0101, 010010, etc.
(c) L = fa2n
j n 0g. Example strings include aaaa, a16, a64, etc.
(d) L = fw j w 2 f0; 1g, w is of the form (0i1)n, for i = 1, 2, ..., n, n 0g. 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 nite automaton for the language specied by the nite automaton
M = (fq0, q1, q2, q3g, f0, 1g, , q0, fq0g) where is dened as follows:
(q0, 0) = q3
(q0, 1) = q0
(q1, 0) = q0
(q1, 1) = q3
(q2, 0) = q2
(q2, 1) = q1
(q3, 0) = q1
(q3, 1) = q2