The DFA Minimizing option

The Minimize option gives guidance in building an equivalent DFA with the minimum number of states. The minimize button is located in the Options menu. Once a DFA is built, select the "Minimize" option in the menubar. A new window will appear in which you can start building the tree to find undistinguishable states. When done with that window a second window will appear in which you can build the minimized DFA.

Note that DFA's are supposed to have a transition leaving from every state for each letter of the machine's alphabet. If any transitions are omitted, then you will have an implicit trap state in your automaton. This implicit state will be added as your last state (but not shown in the Finite Automata window) and will be treated in the tree as if it were in your machine (a reminder will pop up when starting the tree if you have an implicit trap state). This trap state will be removed in the second minimizing window since it is only necessary for distingishing states in the tree.

The Tree Window

The tree window will begin with the two trees (final and nonfinal) already started. The final tree's root will contain a label representing all the final states from the DFA and the nonfinal tree's root will contain a label representing all nonfinal states. For more help on how State labels work see the "NFA to DFA" help. When you are done building the tree click on the "Done" button. The next window will appear if the tree is correct.In the tree window, all the commands are effected using the popup menu (right mouse button)

Distinguishing States

States listed in a node are thus far indistinguishable. To distinguish states in a node N (if this is possible), expand N by creating two or more children and selecting a symbol from the alphabet, say b. For every state in N, calculate the state reachable from N with arc b. If all the reachable states are currently in the same leaf node, then the states in N are thus far still indistinguishable. If the reachable states currently appear in different leaf nodes, then the states in N are distinguishable and grouped into sets based on the groups of their reachable states.

Drawing the Minimum State DFA

The second minimizing window appears with all the states generated by the tree already placed. The only thing that needs to be filled in are the transitions, using the original DFA as a model. You can use the Check done, Solve, and Show options from the menubar to check or finish the machine. They work exactly like the ones in the NFA to DFA window. See the help on NFA to DFA for detailed descriptions of these options.