Note: no late submissions will be accepted for this assignment.
As we discussed in class, a finite state machine is a graph that encapsulates the rules for generating a sequence of symbols (which typically correspond to actions in a process). For example, the figure below (taken from Claude Shannon's classic paper, A Mathematical Theory of Communication), depicts a finite state machine that defines the rules for spacing within a legal Morse code message.
You will define a class named FSM that models a finite state machine using a two-level HashMap. For example, your class might have the following field:
private HashMap<String, HashMap<String, String>> machine;
The keys in machine are the starting nodes of edges in the finite state machine. For each key, the value is another HashMap that maps edge labels to ending states. For example, suppose we represented the edges in the above diagram with the following labels:
inWord . inWord
inWord - inWord
inWord _ betweenWords
inWord __ betweenWords
betweenWords . inWord
betweenWords - inWord
Assuming these edges had been added to the machine field, then this.machine.get("inWord") would access a HashMap representing the four edges. Likewise, this.machine.get("inWord").get("__") would access the value "betweenWords".
FSM class should provide at least the following two methods:
getEndState should take a start state and an edge label, and return the end state that is connected to the start state by that edge. For example, if mach represents the above finite state machine, then mach.getEndState("inWord", "_") should return betweenWords.getEdges should take a start state and an end state, and return a list of the edge labels that connect them. Note that there may be more than one edge connecting two states, so a list is required. For example, if mach represents the above finite state machine, then mach.getEdge("inWord", "betweenWords") should return ["_", "__"].To test your getEndState method, you should implement a driver class named PathFinder that traverses paths in the finite state machine. It should prompt the user for the name of the file representing the finite state machine. You may assume that all state names and edge labels are strings containing no spaces. After reading in the edges from the file, the driver should repeatedly prompt for a starting state in that machine followed by a series of edge labels. It should simulate traversing those edges, starting at the specified state, and report the final state reached. For example:
Enter FSM file: morse.txt Enter a start state (* to end): inWord Enter a step sequence (separated with whitespace): - . - . End state: inWord Enter a start state (* to end): inWord Enter a step sequence (separated with whitespace): - . - . _ . . - __ End state: betweenWords Enter another start state (* to end): inWord Enter a step sequence (separated with whitespace): . _ __ ILLEGAL SEQUENCE Enter another start state (* to end): * DONE
To test your getEdges method, you should implement a driver class named PathChecker that checks the validity of paths in the finite state machine. It should prompt the user for the name of the file representing the finite state machine. You may assume that all state names and edge labels are strings containing no spaces. After reading in the edges from the file, the driver should repeatedly prompt for a sequence of states in that finite state machine and should report whether ther exists a path along each sequence. For example:
Enter FSM file: morse.txt Enter a state sequence (* to end): inWord inWord betweenWords inWord VALID sequence. Enter a state sequence (* to end): inWord betweenWords betweenWords inWords INVALID sequence. Enter another start state (* to end): * DONE
Your code should follow the Model-View-Controller pattern. In particular, the FSM class should not perform any input/output. All file access and user interaction should be handled by the driver classes. In this way, it should be possible to change the views by substituting different controllers (i.e., driver programs).
Your programs should not crash under any circumstances. If the user enters a state or edge name that is not defined, then a message to that effect should be displayed and execution should continue.
All classes should follow standard Java style conventions (e.g., class names start with a capital letter, methods and variables start with lowercase, javadoc comments on each class and method, your name and date in the javadoc comments for each class).