Question

Write Java code to implement a FSM machine that recognizes the language for the alphabet {a,b,c} consisting of all strings that contain two consecutive c's and end with b.

                  Your FSM program should include the following three static methods (Java) or functions (C):

                                          a.    int nextState(int state, char symbol)

                                 A state-transition function that returns the next state based on the

                                 current state and an input symbol. This function should also return

                                 -1 when an invalid input character is detected.

                                 State transition behavior can be stored in a 2-dimensional array

                                 where the first dimension represents the current state and the

                                 second dimension represents the next input character. The entries

                                 for the array are the resulting “next state.”

                                 For example, a FSM that has 4 states and recognizes 3 valid input

                                 characters would be fully characterized by a 4 X 3 state transition

                                 array.

                                          b.         boolean accept(int state)

                                 A output function that returns true if the input state is an acceptance

                                 state and false otherwise.

                                 Acceptance states can be stored in a Boolean one dimensional array

                                 where the single dimension represents the current state. The entries

                                 for the array are either true or false, depending on whether the

                                 corresponding state is an acceptance state.

                                          c.         boolean validString(String word)

                                 A processing function that returns true if the input string is in the

                                 language of the FSM. A string is in the language if it moves the

                                 system from the start state to an acceptance state.

                             

                                 This function should read each of the characters in the input string

                                 in order, and invoke the nextState() method on each iteration.

                                 After every character in the input string has been checked, the

                                 accept(int state) method can be called to determine if the

            final resulting state is an acceptance state.

                        Turn in source code for your main program and functions, plus sample output for the following input strings:

                        a.         aaccbbabc

                        b.         cacbcabbc

                        c.         bcbcccbbb

Answer 1

TestFSM.java

// Test Finite State Machine Class
public class TestFSM
{
public static void main(String[] args)
{

    /*
    // L1
    String A   = "ab";
    int[][] ST = {{1,4},
                  {0,2},
                  {3,5},
                  {2,5},
                  {2,5},
                  {5,5}};
    int[] AS   = {0,0,1,0,0,0};
    */
  
    /*
    // L2
    String A   = "01";
    int[][] ST = {{1,6},
                  {2,5},
                  {3,4},
                  {8,8},
                  {8,8},
                  {3,8},
                  {7,8},
                  {3,8},
                  {8,8}};
    int[] AS   = {0,1,1,1,1,0,0,0,0};
    */
  
    /*
    // L3
    String A   = "xyz";
    int[][] ST = {{1,0,4},
                  {1,2,0},
                  {3,0,4},
                  {3,3,3},
                  {0,5,4},
                  {1,0,6},
                  {6,6,6}};
    int[] AS   = {0,0,0,1,0,0,1};
    */
  
    // L4
    String A   = "pqr";
    int[][] ST = {{4,0,4},
                  {4,2,1},
                  {4,0,3},
                  {3,3,3},
                  {5,0,1},
                  {5,0,1}};
    int[] AS   = {0,0,0,1,0,1};

    String inString;
    boolean accept1 = false;
    FSM FSM1 = new FSM(A, ST, AS);
    if(args.length >= 1)
    {
      // Input string is command line parameter
      inString = args[0];
      accept1 = FSM1.validString(inString);
      System.out.println("\n String: " + inString
        + "    Accept? " + accept1);
    }
} // end main

} // end class

FSM.java

// Finite State Machine Class
public class FSM
{
// Instance variables
public String alphabet;
public int    stateTrans[][];
public int    acceptState[];
private int    cstate;

// Constructor function

public FSM(String A, int[][] ST, int[] AS)
{
    int NSYMBOLS = A.length();
    int NSTATES = AS.length;
    // Alphabet
    alphabet = "" + A;
    // State transition table
    stateTrans = new int[NSTATES][NSYMBOLS];
    for(int r = 0; r < NSTATES; r++)
      for(int c = 0; c < NSYMBOLS; c++)
        stateTrans[r][c] = ST[r][c];
    // Accept states
    acceptState = new int[NSTATES];
    for(int r = 0; r < NSTATES; r++)
      acceptState[r] = AS[r];
    // Start state
    cstate = 0;
}

// Methods

public int getState()
{
    return cstate;
}

public void setState(int state)
{
    cstate = state;
    return;
}

public int nextState(char symbol)
{
    int nstate = -1;
    int col = alphabet.indexOf(symbol);
    if(col >= 0)
      nstate = stateTrans[cstate][col];
    return nstate;
}

public boolean accept(int state)
{
    if(state < 0)
      return false;
    return (acceptState[state] != 0);
}

public boolean validString(String word)
{
    cstate = 0;
    for(int k = 0; k < word.length(); k++){
      cstate = nextState(word.charAt(k));
      if(cstate < 0)
        return false;
    }
    return accept(cstate);
}

} // end class

Problems @ Javadoc Declaration Console 3 teminateds TestFSM [Java Application] C:Program Files Javaljrel.8.0 201\binljavaw.exe (Apr 15, 2019, 12:04:35 AM) String: aaccbbabc Accept? false