Once a finite automaton is constructed, we can use a general purpose program
to simulate its operation. One such simulation algorithm is given below.
It uses four arrays. One array, called TOKEN, stores for each state the input
symbols that trigger transitions from the state. Another array, called NEXT_STATE,
holds the next state for each input symbol for each state. A third array,
called ACTION, indicates the actions taken at each state and
a fourth, called STATEX, keeps the index of the first symbol
in the TOKEN array for each state. Those indices are used to access
the contents of
the other arrays.
Algorithm FA Simulator
state := INITIAL_STATE;
input := read_input( ) ; while ( state
NO_of_STATES and not End of Input )
index := STATEX [state] ; while ( TOKEN [index] 0
and TOKEN [index] input )
index := index + 1;
if ( TOKEN [index] 0 )
perform the action specified by ACTION [index];
state := NEXT_STATE [index];
input := read_input( ) ;
Here 0 in the TOKEN array is a marker between states.
To see how this algorithm works, first click the box pointed by the red arrow in the figure below.
Then type in a number you want the FA to recognize.
You must hit the "Tab" key to move to the next box. For example, to input 3.45, first click the box under the red arrow. Then
type 3 Tab . Tab 4 Tab 5.
Then every time you click "SHOW" the number is processed digit by digit.
The corresponding transitions are going to be shown by red arrows in the transition diagram.
In the DFA below all the transitions to the empty state (i.e. empty transitions) are omitted.
The ACTION array would contain pointers to actions to be taken corresponding to arcs traversed such as
converting a digit in BCD form to the corresponding binary number.
At the moment
it is empty. So no action is taken as a number is processed.
S is the initial state and B and H are accepting states.
The numbers below NEXT_STATE array show the correspondence between the indices of
the STATEX array and the states A, B, C and H. S corresponds to 1.
If you are also interested in how code is executed.
It is extremely slow. So be patient.