Question 2. Let = {a,b,c}. Let L = { w | w = s1s2 ... sk for k 0 and si = xiyi where each xi consists of any number of as (that is zero or more), and each yi consists of either the empty

string or: bb followed by any number of repetitions of symbol c (that is zero or more)} a) Prove that L is regular by designing a NFA N that satisfies the following constraints:

N = (Q, , , q0, F) with |Q| = 3 (that is N has exactly three states), = {a,b,c}, F = {q0}. Use a state diagram to show .

b) Give a DFA D with L(D) = L(N) = L. To build D, follow exactly the algorithm of the DFA design in the proof of the theorem For every NFA there exists an equivalent DFA discussed in class. Show your steps. Give the transition table to describe Ds transition function.

c) How many states of DFA D from your answer in b) can be removed from D without changing its language?

Question 3. a) Give a sequence of states for automaton N from Question2.

a) above, and string w = aaabbc that causes N to accept w.

b) Give a sequence of states for N that does not cause N to accept w. c) Is w L(N)?