Given a DFA = (, , , 0 , ) that recognizes a regular language , construct an NFA = (, , , 0 , ) such that:

The states of are the same as the states of . The start state of is the same as the start state of . = {0 }. That is, the accepting states of are the accepting states of and the start state.

is defined as follows for any and any : (, ) = { (, ) if or (, ) {0 } if and = That is, the transitions of are the transitions of and -transitions from the accepting states of to the start state.

a. Show, by giving a counterexample, that this construction fails to prove that the class of regular languages is closed under Kleene star. That is, show that if is a DFA that recognizes a regular language , then this construction may not result in an NFA that recognizes the Kleene star of . Justify your answer. Hint: give a specific DFA = (, , , 0 , ) for which the constructed NFA = (, , , 0 , ) does not recognize the Kleene star of the language of .

b. Explain how to fix this construction to prove that the class of regular languages is closed under Kleene star.