Regular Expression
Input Window
Regular Expression Input Window
To convert from a Regular Expression to a FSA, one must first
input the Regular Expression into the Regular Expression Input
Window. Then press "Create FSA" to begin creating the
Automata.
NOTE: Lambda transitions can be inputted by entering the "!" character.
The Conversion Algorithm
Converting from a Regular Expression to a FSA involves a specific
algorithm. The conversion involves the presentation of each part
of the Regular Expression inputted until the entire Regular
Expression has been constructed.
In order to construct the FSA, the algorithm follows several rules which the user must also conform to in order to allow the checking procedure to work correctly. The rules used by the algorithm may have extraneous parts in some cases, but they are necessary in specific instances. Thus, the algorithm will produce a non-minimal, but correct, FSA.
The following are the rules that the Regular Expression and the user must follow:
All Input Symbols in the regular expression are automatically converted into a transition from a starting state to an ending state. The transition is given the value of the input symbol. For example, the regular expression "b" would be converted to:
Concatenation is handled by adding a lambda transition between the final state of the first FSA to be concatenated and the starting state of the second symbol to be concatenated. For example, the regular expression "ba" would be converted as follows:
Building the FSA from the Regular Expression
Once the Regular Expression has been inputted and the Create
FSA button is pressed, a new FSA window appears for the
creation of the FSA. In the main toolbar, the message
"Create the Regular Expression: " followed by a Regular
Expression to create is displayed. This Regular Expression tells
what subexpression of the Regular Expression that was inputted
should be made at the present step. The idea is to gradually
build the finished FSA from the ground up. Automatically, the
starter FSAs for each variable used in the conversion are added
to the FSA window. Thus, what the user needs to do is to connect
up the starter FSAs in the method described above (possibly
adding new states if necessary).
Under the Solve menu, there are several options:
Before one can continue on to the next step of this conversion, it is required that the current step is correct. As a result, selecting Next Step when the current Regular Expression has not been finished will not work.