Programming in Java: Finite State Machine Emulator

A finite state machine is a computational model consisting of a finite number of states and transitions between those states, possibly with accompanying actions. For this project I developed a finite state machine emulator in Java that models the entities in the FSM model.

As an example the emulator is modeled after:

Below is outlined sections of the program. Download the entire source as an Eclipse IDE project at the bottom of the page.

The following class “MainFSMEmulator” presented here contains the setup and example of the diagram above:

public class MainFSMEmulator {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		// Viable inputs
		String inputA = "a";
		String inputB = "b";

		// State q1
		Map<String, Transition> q1Transitions = new HashMap<String, Transition>();
		q1Transitions.put(inputA, new Transition("0", "q1"));
		q1Transitions.put(inputB, new Transition("1", "q4"));
		State q1 = new State(q1Transitions, "q1");

		// State q2
		Map<String, Transition> q2Transitions = new HashMap<String, Transition>();
		q2Transitions.put(inputA, new Transition("0", "q1"));
		q2Transitions.put(inputB, new Transition("1", "q5"));
		State q2 = new State(q2Transitions, "q2");

		// State q3
		Map<String, Transition> q3Transitions = new HashMap<String, Transition>();
		q3Transitions.put(inputA, new Transition("0", "q5"));
		q3Transitions.put(inputB, new Transition("1", "q1"));
		State q3 = new State(q3Transitions, "q3");

		// State q4
		Map<String, Transition> q4Transitions = new HashMap<String, Transition>();
		q4Transitions.put(inputA, new Transition("1", "q3"));
		q4Transitions.put(inputB, new Transition("1", "q4"));
		State q4 = new State(q4Transitions, "q4");

		// State q5
		Map<String, Transition> q5Transitions = new HashMap<String, Transition>();
		q5Transitions.put(inputA, new Transition("1", "q2"));
		q5Transitions.put(inputB, new Transition("1", "q5"));
		State q5 = new State(q5Transitions, "q5");

		// State map for our Finite State Machine
		Map<String, State> states = new HashMap<String, State>();
		states.put(q1.getStateKey(), q1);
		states.put(q2.getStateKey(), q2);
		states.put(q3.getStateKey(), q3);
		states.put(q4.getStateKey(), q4);
		states.put(q5.getStateKey(), q5);

		// The starting state of our Finite State Machine
		String initialStateKey = "q1";

		// Test our finite state machine
		try
		{
			// Build the Finite State Machine
			FiniteStateMachine fsm = new FiniteStateMachine(states, initialStateKey);

			// Run our input string;
			LinkedList<String> inputString = new LinkedList<String>();
			inputString.add("b");
			inputString.add("a");
			inputString.add("a");
			inputString.add("a");

			Iterator<String> itr = inputString.iterator();
			while (itr.hasNext()) {

				try
				{
					fsm.input(itr.next());
				}
				catch(UnknownInput e)
				{
					e.getMessage();
				}
			}
		}
		catch(UnknownState e)
		{
			e.getMessage();
		}

		System.out.println("Program ending.");
		System.exit(0);
	}
}

Above I am setting up the finite state machine model example diagrammed using a series of created objects to represent the FSM states, transitions and the machine itself. But how doe we know it models anything? Well the above program also sets up a series of inputs of either “a” or “b” to test the machine with. Building and running the source with an input string of “aaba” outputs:

FSM Initialized. Starting state is: q1
CurrentState(q1)
	Input(a) -> Output(0) -> NextState(q1)
CurrentState(q1)
	Input(a) -> Output(0) -> NextState(q1)
CurrentState(q1)
	Input(b) -> Output(1) -> NextState(q4)
CurrentState(q4)
	Input(a) -> Output(1) -> NextState(q3)
CurrentState(q3)
Program ending.

You can see that the output models that which the diagram indicates for the transitions. Feel free to download the source code and analyze the objects and how they can simply model a finite state machine. My experience with this project was that finite state machines are great for modelling software processes. So great in fact that I found it easier to express an FSM through code than through English.

Download: FSMEmulator.zip