Finite Automata

Simulation of Finite Automata



Subjects to be Learned

Contents


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];

        else error

        input := read_input( ) ;


end

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. click here
It is extremely slow. So be patient.





Next -- Non-Regular Languages

Back to Study Schedule

Back to Table of Contents