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:
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.