Compiler : Finite State Machine code sample

Sample 0 : 

import java.io.*;

import java.util.*;

/*

String containing an even number of one

    0   1

------------

A*  A   B

B   B   A

------------

*/

public class FSM

{

    final static int STATES=2, INPUTS=2;

   

    public static void main (String[] args) throws IOException{

       

        boolean [] accept = new boolean[STATES];

        int [][] fsm = new int[STATES][INPUTS];

        accept[0] = true;

        accept[1] = false;

       

        fsm[0][0] = 0;

        fsm[0][1] = 1;

        fsm[1][0] = 1;

        fsm[1][1] = 0;

       

        // State A = 0, State B = 1

        int inp = 0;

        int state = 0;

       

        try{

            inp = System.in.read() - '0';

           

            while(inp >= 0 && inp < INPUTS){

                state = fsm[state][inp];

                inp = System.in.read() - '0';

            }

        }

        catch(IOException ioe){

            System.out.println("IO error " + ioe);

        }

       

        if(accept[state]){

            System.out.println("Accepted");   

        }else{

            System.out.println("Rejected");

        }

       

    }

}

Sample 1 : Strings containing exactly three zeros (the input alphabet is {0,1}) 

Explanation:

1. States Definition:

   • State 0: Initial state, no zeros seen.
   • State 1: One zero seen.
   • State 2: Two zeros seen.
   • State 3: Exactly three zeros seen (accepting state).
   • State 4: More than three zeros seen (rejecting state).

2. Transitions:

   • From State 0:
     • On input '0', transition to State 1.
     • On input '1', stay in State 0.
   • From State 1:
     • On input '0', transition to State 2.
     • On input '1', stay in State 1.
   • From State 2:
     • On input '0', transition to State 3.
     • On input '1', stay in State 2.
   • From State 3:
     • On input '0', transition to State 4.
     • On input '1', stay in State 3.
   • From State 4:
     • On input '0' or '1', stay in State 4 (as we have seen more than three zeros).

3. Accepting State:

   • Only State 3 is accepting, meaning the input string is accepted only if it contains exactly three zeros.

Usage:

• The program reads input characters one by one and transitions between states based on the input.
• Once input reading is complete (when a non-binary character is encountered), the program checks the final state.
• If the final state is the accepting state (State 3), it prints "Accepted".
• Otherwise, it prints "Rejected".

Sample 2 : Strings containing four consecutive a’s (the input alphabet is {a,b})

Explanation:

1. States Definition:

   • State 0: Initial state, no 'a's seen.
   • State 1: One consecutive 'a' seen.
   • State 2: Two consecutive 'a's seen.
   • State 3: Three consecutive 'a's seen.
   • State 4: Four consecutive 'a's seen (accepting state).

2. Transitions:

   • From State 0:
     • On input 'a' (converted to 0), transition to State 1.
     • On input 'b' (converted to 1), stay in State 0.
   • From State 1:
     • On input 'a', transition to State 2.
     • On input 'b', transition back to State 0.
   • From State 2:
     • On input 'a', transition to State 3.
     • On input 'b', transition back to State 0.
   • From State 3:
     • On input 'a', transition to State 4.
     • On input 'b', transition back to State 0.
   • From State 4:
     • On input 'a' or 'b', stay in State 4 (accepting state, remains accepting).

3. Accepting State:

   • Only State 4 is accepting, meaning the input string is accepted if and only if it contains a sequence of exactly four consecutive 'a's.

Usage:

• The program reads input characters one by one and transitions between states based on the input.
• Once input reading is complete (when a non-'a' or non-'b' character is encountered), the program checks the final state.
• If the final state is the accepting state (State 4), it prints "Accepted".
• Otherwise, it prints "Rejected".

Sample 3 : (a+b)*.(c+d) 

Explanation:

1. States Definition:

   • State 0: Initial state, accepting (a+b)*.
   • State 1: After seeing the first c or d.
   • State 2: Accepting state after seeing c or d.

2. Transitions:

   • From State 0:
     • On input 'a' or 'b', stay in State 0.
     • On input 'c' or 'd', move to State 1.
   • From State 1:
     • Any input ('a', 'b', 'c', or 'd') leads to State 2.
   • From State 2:
     • Stay in State 2 for any input.

3. Accepting State:

   • State 2 is accepting, meaning the input string is accepted if and only if it ends with either c or d after any sequence of as and bs.

Usage:

• The program reads input characters one by one and transitions between states based on the input.
• Once input reading is complete (when a non-'a', non-'b', non-'c', or non-'d' character is encountered), the program checks the final state.
• If the final state is the accepting state (State 2), it prints "Accepted".
• Otherwise, it prints "Rejected".