// Finite State Machine Class public class FSM { // Instance variables public St
ID: 3821459 • Letter: #
Question
// 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
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
Explanation / Answer
public class Ant
{
public var position :Vector3D;
public var velocity :Vector3D;
public var brain :FSM;
public function Ant(posX :Number, posY :Number) {
position = new Vector3D(posX, posY);
velocity = new Vector3D( -1, -1);
brain = new FSM();
// Tell the brain to start looking for the leaf.
brain.setState(findLeaf);
}
/**
* The "findLeaf" state.
* It makes the ant move towards the leaf.
*/
public function findLeaf() :void {
}
/**
* The "goHome" state.
* It makes the ant move towards its home.
*/
public function goHome() :void {
}
/**
* The "runAway" state.
* It makes the ant run away from the mouse cursor.
*/
public function runAway() :void {
}
public function update():void {
// Update the FSM controlling the "brain". It will invoke the currently
// active state function: findLeaf(), goHome() or runAway().
brain.update();
// Apply the velocity vector to the position, making the ant move.
moveBasedOnVelocity();
}
(...)
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.