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.

Problem 4

Here is the output machine $M'$ and $w$ table from the Augmented DFA Minimization algorithm run on some input, which I'm not showing you.

Machine $M'$	$w$ table
	$w_{i,j}$ 1 2 3 4 5 6 1 $ab$ $b$ $b$ $\lambda$ $\lambda$ 2 $b$ $b$ $\lambda$ $\lambda$ 3 $bb$ $\lambda$ $\lambda$ 4 $\lambda$ $\lambda$ 5 $b$ 6

Consider the machine $M_{new}$ below, which has only five states, and show how the CounterExampleFinder algorithm would produce a string that proves that $M_{new}$ accepts a different language than $M'$. [Hint: Check out "Running CounterExampleFinder" in the notes.]