// 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

for(int c = 0; c

stateTrans[r][c] = ST[r][c];

// Accept states

acceptState = new int[NSTATES];

for(int r = 0; 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

return false;

return (acceptState[state] != 0);

}

public boolean validString(String word)

{

cstate = 0;

for(int k = 0; k

cstate = nextState(word.charAt(k));

if(cstate

return false;

}

return accept(cstate);

}

} // end class

The FSM java file defines a finite state machine class. This class file includes the following instance variables: String alphabet set of input symbols int state Trans state transition table -1 if accept state int accept State 0 otherwise int cstate Current State The FSM class includes methods to construct a FSM object and to get and set the current state. It also includes the following methods: int next State (char symbol) Calculates the destination state in a state transition. boolean accept (int state) Returns true if the designated state is an accept state. boolean validstring (String word) 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 accept state. You do not need to add any code to the FSM class. For each of the four FSMs in Part A, write a test program that uses the FSM class to instance an object, and determine which of the following strings are in the language of the FSM. LI: aabaaaa aaaba aaa aabaa aab baaaaaa, aaaaabaa 12: 10, 00, 010 101, 0100 L3: xyzyzyzy xzzxzxyy, yzxyzyyz, z zyzxyxx, LA: qapprarr, parprppa, rparrapp, papprpqq, grpprgrp