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:

- Or Operator (+) is handled by adding a new initial state and two lambda transitions. One lambda transition goes from the new starting state to the starting state of the first FSA to be ORed. The other lambda transition goes from the new starting state to the starting state of the second FSA to be ORed. For example, the regular expression "b+a" would be converted as follows:

- Kleene Star(*) is handled by adding a new starting state, making this new starting state a final state, and adding two lambda transitions. One lambda transition goes from the final state(s) of the FSA to be Kleene Starred to the starting state of the FSA to be Kleene Starred. The second lambda transition goes from the new starting state to the starting state of the FSA that is to be Kleene Starred. For example, the regular expression "b*" 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:

- Check if Done - verifies that the FSA representing the regular expression at the current step is finished
- Show - shows the correct FSA for the current step in the FSA creation
- Show All - shows the final resulting FSA after all of the conversions have been performed
- Next Step - moves on to the next step of the conversion by presenting a different sub-expression that needs to be evaluated

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.