Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Run the state minization algorithm on the following machine, and draw the resulting minimized machine.
 

Problem 2

Consider the machine M2 below. It does not conform to our State Minimization Algorithm input requirements becuase there are states are not reachable and the machine actually accepts the empty language. None the less, trace through the State Minimization algorithm and draw the machine it produces. Does the algorithm truly give the "minimum machine" when there are unreachable states like this?

 

Problem 3

You can use the State Minimization algorithm to determine whether or not the language accepted by an arbitrary DFA is empty. In a few words, outline the process.