Converting a NFA to a DFA


Converting to a 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 nondeterministic finite automaton (NFA) into a deterministic automaton (DFA) by using the tools under the “Convert → Convert to DFA” menu option.

To get started, open JFLAP. Then, either load the file nfaToDfa.jff, or construct the nondeterministic finite automaton present in the screen below. When finished, your screen should look something like this:

Converting to a DFA

We will now convert this NFA into a DFA. Click on the “Convert → Convert to DFA” menu option, and this screen should come up:

The NFA is present in the panel on the left, and our new DFA is present in the screen to the right. Let's begin building our DFA. First, hold the mouse over the second button in the toolbar from the left to see the description of the button, which should be “Expand Group on (T)erminal”. Click on that button, and then click and hold down the mouse on state q0. Then, drag the mouse away from the state, and release it somewhere in the white part of the right panel. Enter “a” when you are prompted for the terminal, and “0,1,2” when prompted for the group of NFA states. When finished, your screen should contain something like this (Note: one may adjust the states so that the layout resembles this image):

You are probably curious about what exactly we just did. Basically, we just built the first transition in our DFA. In our NFA, we start at state “q0”. This is represented in the DFA through the “0” label in DFA state “q0”. The DFA's “a” expansion represents what happens when processing an “a” in the NFA. However, in the NFA there are three possible states we can proceed to when processing an “a”, NFA states “q0” and “q1”, and “q2”. This multiplicity of possibilities is represented by the label under DFA state “q1”, which is “0,1,2” (standing for NFA states “q0”, “q1”, and “q2”).

You should note that it is not possible to expand a state on a terminal that does not have a corresponding path in the NFA. For example, if one tries the same method above on state “q0”, but instead uses the terminal “c”, an error message will pop up.

Now we can add two more transitions in the DFA. Through the same method as before, add another expansion, starting from “q1”. The terminal value will be “b” and the states will be “1,3”. This will create a new state “q2”. Now, add an expansion starting from “q2”. This time, however, release the mouse on “q2” and enter the terminal “a”. When finished, something resembling the following should be present on your screen:

From NFA state “q1”, there are no expansions leading from it that contain a “b”. From NFA states “q0” and “q2”, a “b” will allow the program to reach NFA states “q1” or “q3”. Thus, the label for DFA state “q2” is “1,3”. You also might notice that DFA state “q2” is a final state. Since NFA state “q3” is a final state, and DFA state “q2” represents a possible path to NFA state “q3”, DFA state “q2” is a final state. It does not matter that DFA state “q2” also represents a possible path to NFA state “q1”, a nonfinal state. As long as one possible path represented by a DFA state is final, the DFA state is final. In the case of the expansion from “q2” to “q2”, since in DFA state “q2” one can be at NFA states “q1” or “q3”, and since processing any “a” from there will result in being in one of those two NFA states, the expansion does not result in a DFA state change.

Let's check and see if we are done. Go ahead and click on the “Done?” button. The message will tell us that we still have some work to do, as we have two more states and seven more transitions unaccounted for in the DFA. Go ahead and finish it. One can utilize, if desired, two other buttons in the toolbar. The “(S)tate Expander” button, if pressed, will fill out all transitions and create any new DFA states those transitions require when you click on an existing DFA state. Alternatively, if one wants to see the whole DFA right away, one can click on the “Complete” button. If either of these are pressed, the layout manager may not put everything onto the part of the screen currently visible, so one may have to maximize the window or find all states using the sliders. After finishing the DFA, and perhaps after moving the states around a little, you should have a picture resembling the following:

Now click the “Done?” button again. After a message informing you that the DFA is fully built, a new editor window is generated with the DFA in it. Congratulations, you have converted your NFA into a DFA!

This concludes our brief tutorial on converting NFAs into DFAs. Thanks for reading!