Let = {a,b,c}. Let L = { w | w = s1s2 sk for k 0 and si = xiyi where each xi consists of any number of a's (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?