The FSA to Regular Expression Options

When converting from FSA to Regular Expression, the following recursive formula is followed:

R(i, j, k + 1) = R(i, j, k) + R(i, k, k) R(k, k, k)* R(k, j, k)

Where the result of R(a, b, c) is the Regular Expression between a and b without going through a state numbered greater than or equal to c. The stopping condition for this recursive function is shown below:

Starting Values Dialog
When the "Convert to Regular Expression" menu is pressed inside the FSA window, the Starting State Window is displayed.

Within this window the R(a, b, c) expressions are displayed. The R(a, b, c) values correspond to each final state. The input fields for each final state correspond to the a, b, and c values in the R(a, b, c) expression. Below is an summary of what a, b, and c equal:

This gives the algorithm a starting point. For each final state, there are three input fields for each of the three variables. From this dialog several options are available:

Recursive Conversion Window
Once the initial values have been inputted the Recursive Conversion Window appears to perform the actual conversion. This window consists primarily of a listbox displaying all of the recursive R(a, b, c) function calls beginning with the starting values. Each level of equations is separated by a divider. Levels are defined as all equations of the form R(a,b,c) with the same value for c. Each level consists of equations from the level below it. Thus, the highest levels are at the top and the lowest levels are at the bottom. Actual evaluation of equations begins at the bottom and continues upwards.

The options available from this dialog are:

There are two phases of the conversion:

  1. the down pass which fills in function dependencies
  2. the up pass which fills in the actual values of the functions and performs simplification.

During the down pass, the pressing the "Next Expansion" button will show the functions that make up the selected function by highlighting the function being looked at and highlighting the functions that compose it. Once the lowest level of recursive function calls is reached, the up pass begins. An input box appears allowing the user to input the value (if it is the lowest level function) or the simplified expression (if it is a composite function). The user is also given the ability to show the answer or check the answer.

NOTE: Lambda transitions are represented as the "!" character.

During the up pass, each composite function will be replaced with the values of the functions that it is composed of. This is shown immediately below the function in the list. The next line shows the simplified expression that the user must input.

Once the last recursive function call is evaluated, the answer is shown at the top.

NOTE: Conversion to Regular Expression results in a Regular Expression that is equivalent to the FSA. Some simplifications are done, but it is not guaranteed to produce the simplest Regular Expression in all cases.