1 consider the deterministic finite automaton m q1 q2 q3 0

Question

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

Answer 1

I need help in the given Theory of computation problem. Please provide me the method to solve the problem. Q1: Take the deterministic finite automaton M = ({q1, q2, q3}, {0, 1}, ?, q1, {q2}) which is defined as follows: • (q1, 0) = q1 • (q1, 1) = q2 • (q2, 0) = q3 • (q2, 1) = q2 • (q3, 0) = q2 • (q3, 1) = q2 Provide an equivalent regular expression. Q2. Prove that the given languages are not regular sets: a) L = faibjck j i = 0 _ j = k, i; j; k 0g. Illustration strings comprise bccc, abbcc, aaa, etc. b) L = fww j w 2 f0; 1g+g. Illustration strings comprise 00, 11, 0101, 010010, etc. c) L = fa2n j n 0g. Illustration strings comprise aaaa, a16, a64, etc.