Converting a FA to a Regular Expression
Introduction
Converting to a Regular Expression
This section specifically describes how one may transform any finite automaton into a regular expression by using the tools under the “Convert → Convert FA to RE” menu option. For knowledge of many of the general tools, menus, and windows used to create an automaton, one should first read the tutorial on finite automata. For knowledge of regular expressions and how JFLAP defines and implements them, one should first read the tutorial on regular expressions.
To get started, open JFLAP. Then, either load the file dfaToRegExpr.jff, or construct the finite automaton present in the screen below. When finished, your screen should look something like this:
Converting to a Regular Expression
We will now convert this DFA into a regular expression. Click on the “Convert → Convert FA to RE” menu option, and this screen should come up:
You can see that this is a fairly simple automaton, and that we are prompted for 4 new transitions. If this were a more complex automaton, with multiple final states, we would first have to create a single final state and then establish “λ” transitions between the old final states and the new final state. Also, if there was more than one transition between two states, we would have to use the “Transition (C)ollapser” button (fourth from left) to transform multiple transitions into one transition. This is done simply by clicking on the transition, and multiple transitions will be linked by union operators inside one transition. For example, multiple transitions of “a” and “b” will become the solo transition “a+b”. Doing these steps is fairly straightforward, so for the sake of simplicity we will not use such an example utilizing them.
What exactly are the 4 transitions that we need to add, and why do we need to add them? Before the conversion algorithm can work, every state must have a transition to every state in the graph, including itself. Thus, the total number of transitions for a finite automaton with n states must be n2. In this example, since there are 3 states, there should be 9 transitions. Since, however, the transitions that aren't currently defined are never taken, the transitions that we add will always be on the empty set of strings, or ∅. Now, let's add the 4 transitions. Add transitions from “q1” to “q1”, “q2” to “q2”, “q2” to “q0”, and from “q1” to “q0” by first clicking on the “(T)ransition Creator” button (third from left) and then on the appropriate places on the screen. When finished, the screen should resemble the one below...
Now the message has changed, and it tells us to use the collapse state tool. This tool is accessed using the fourth button from the left, the “State (C)ollapser” button. Click on that and then try to click on either state “q0” or “q1”. You should be informed that the final or initial state cannot be removed (whichever one you clicked on). Thus, the only state that can be removed is “q2”. Thus, click on that state. Once you click on it, a “Transitions” window should come up, which lists all the transitions and labels that will be present in the current graph once the current state has been removed. If you click on the individual rows in the window, the old transitions in the editor window that correspond to the new transition will be highlighted, in addition to the state that will be removed. The screen below is an example of both the Transition window, highlighted old transitions, and the highlighted state to be removed (in a resized main window).
Click on “Finalize” and the “Transitions” window will disappear. The following screen should now be visible, with the new regular expression under the “Generalized Transition Graph Finished!” label. Note that since the generalized transition graph has only 2 states, it is easy to figure out the regular expression. It consists of all cycles from “q0” to “q0” [(a*b(ab)*aa)*], followed by the loop transition on “q0” zero or more times [a*], followed by the transition from “q0” to “q1” [b], and concluding with the loop transition on “q1” zero or more times [(ab)*]. Concatenating them together, you will have the regular expression [(a*b(ab)*aa)*a*b(ab)*]. Click on the “Export” button, and you will now have this new regular expression to use as you see fit.
This concludes our brief tutorial on converting FAs into regular expressions. Thanks for reading!