Converting a DFA to a Minimal State DFA
Introduction
Converting
to a Minimal DFA
It is recommended, if you haven't already, to read the tutorial about creating a finite automaton, which covers the basics of constructing a FA. This section specifically describes how one may transform any deterministic finite automaton (DFA) into a minimal state deterministic finite automaton (a DFA with a minimal number of states) by using the tools under the “Convert → Minimize DFA” menu option.
To get started, open JFLAP. Then, either load the file dfaToMinDFA.jff, or construct the nondeterministic finite automaton present in the screen below. You may have to resize your screen a little if the whole graph does not fit onto the screen. When finished, your screen should look something like this:
We will now convert this DFA into a minimal state DFA. Click on the “Convert → Minimize DFA” menu option, and this screen should come up:
The DFA is present in the panel on the left, and a tree of states is present in the screen to the right. You might wonder what exactly the tree nodes and labels in the right panel mean. At present, in the root node, all states in the original DFA are represented. In the tree we group all the states from the DFA together in the root of the tree. Then examining these states we look for ways to distinguish them. If we can distinguish states in a node, then we split a node into two or more nodes of states that are distinguished from each other. One way to do this is to divide states in a leaf node and assign them to new children of the node according to their outcomes when grouped along a terminal. We can repeat this until there are no more splits. At that time, the leaf nodes represent the states in the minimal DFA. If a leaf node has multiple states from the original DFA, these states can be combined in the minimal DFA.
Before splitting along terminals, we first split the nodes into “Final” and “Nonfinal” groups. If a state in the DFA is a final state, it is represented in the “Final” node in the minimal DFA as part of the “Final” node's label. As shown, only “q6” in the DFA is a final node, so only a “6” is in the “Final” node label. The same can be applied for nonfinal DFA states and the “Nonfinal” node. The “Nonfinal” node has the values “0, 1, 2, 3, 4, 5” because all other DFA states are nonfinal.
Let's begin splitting the leaf nodes in the tree of states. First, click on the “Nonfinal” node. You will probably notice that all the DFA states represented by the “Nonfinal” node are highlighted to the left and that some buttons are now visible. Click on one of the newly visible buttons, “Set Terminal”. A pop-up will appear prompting for a terminal. Enter the letter “b”. Instead of something happening to the node, a warning message will appear stating that the group doesn't split on that terminal. This is because there is no transition containing a “b” pointing from a member of the “Nonfinal” group to a member of any other group. All transitions that contain a “b” either change between states within the group or else point into the group from outside it.
Now, try to expand on the terminal “a”. When this happens, one will see two child nodes issuing from the “Nonfinal” node. Our task now is to divide the nodes present in “Nonfinal”. We will move to one child all the states which on an “a” terminal end up in state 6 (one group of states in a leaf node), and move to the other child all the states wihch on an “a” terminal end up in states 0-5 (the other group of states in a leaf node). States “q0” and “q4” both transition along the terminal “a” to “q6”, the only node not in the “Nonfinal” group. Thus, “q0” and “q4” need to be in one child. Click on the right child, and then click on “q0” and “q4” in the left panel. Next, click on the left child and then click on the remaining “Nonfinal” states in the left panel. When finished, press the “Check Node” button to receive a message stating whether the expansion is correct. If so, the tree should look like this...
Now, let's finish the minimal DFA. Click on the left child node, and select the “Auto Partition” or “Complete Subtree” buttons. The difference between the two buttons is that “Auto Partition” will simply figure out a division for the currently selected child, while “Complete Subtree” will complete all divisions for which the selected node is an ancestor. Whichever one is clicked, the nodes in the leftmost leaf will now divide according to the terminal “b” (although it might also divide according to terminal “a”). When done, click the newly visible “Finish” button, and the states in the minimal DFA will be shown (note: the states may be in different places on the screen than in the caption below).
|
Complete tree |
New minimal states |
|---|---|
|
. |
|
We now need to add the transitions. Let's have our first one be from “q2” to “q3” along the terminal “a”, which will represent the transitions from both “q0” and “q4” to “q6” along “a” in the original DFA. Click on the transition button, the second one from the left in the button toolbar, and create the transition. Once done, go ahead and add the rest of the transitions. If you get stuck, feel free to utilize the “Hint”, “Complete”, or “Done?” buttons. The “Hint” button will fill in one transition that needs to be completed, the “Complete” button will fill in all remaining transitions, and the “Done?” button will inform you of how many transitions you have remaining. Note also that if you try to create a transition that doesn't exist in the original DFA, such as between “q2” and “q3” along terminal “b”, then an error message will come up. When finished, your picture should resemble the one below:
Now, to export the file, click on the “Done?” button. After seeing a message stating that the minimal DFA is complete, the minimal DFA should be present in a new window.
This concludes our brief tutorial on converting DFAs into minimum DFAs. Thanks for reading!