Note: late submissions will not 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. The edges of the finite state machine can be represented in a file as shown to the right (where the two states are labeled
|inLetter . inLetter
inLetter - inLetter
inLetter _ betweenLetters
inLetter __ betweenLetters
betweenLetters . inLetter
betweenLetters - inLetter
You will define a class named
FiniteStateMachine that models a finite state machine using a two-level
HashMap. The keys in the map are the labels of states that have edges coming out of them and the values represent those edges. Each value is itself a map, with the edge label as the key and the ending state as the value. For example, the Morse code finite state machine above would be represented by the following map of maps:
A skeleton of the
FiniteStateMachine class is provided in FiniteStateMachine.java. Implement the missing methods and thoroughly test your code before moving on to part 2.
Implement a driver class named
PathTracer that traverses paths in a finite state machine. It should prompt the user for the name of the file representing the finite state machine. Each line in the file represents an edge, with strings representing the starting state, edge label, and ending state, respectively. After reading in the edges and adding them to a
FiniteStateMachine<String, String> object, the driver should repeatedly prompt for a starting state in that machine followed by a sequence of edge labels. It should traverse 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): inLetter Enter a step sequence (separated with whitespace): - . - . End state: inLetter Enter a start state (* to end): inLetter Enter a step sequence (separated with whitespace): - . - . _ . . - __ End state: betweenLetters Enter another start state (* to end): inLetter Enter a step sequence (separated with whitespace): . _ __ ILLEGAL SEQUENCE Enter another start state (* to end): * DONE
The following method in the provided
FiniteStateMachine class performs a breadth-first search to find a path from one state to another.
Create a separate driver class named
PathFinder that similarly reads in the definition of a finite state machine and performs searches on that machine. It should repeatedly prompt the user for start and ending states, then call the
findPath method and print the resulting path. For example:
Enter FSM file: change.txt Enter a start state (* to end): 0cents Enter the end state: 35cents State path: [0cents, 10cents, 35cents] Enter a start state (* to end): 5cents Enter the end state: 25cents State path: [5cents, 15cents, 25cents] Enter another start state (* to end): 10cents Enter the end state: 5cents NO SUCH PATH Enter another start state (* to end): * DONE
FOR EXTRA CREDIT: you may add additional functionality to your program so that it also displays the edge labels on the reported path. For example:
Enter a start state (* to end): 0cents Enter the end state: 35cents State path: [0cents, 10cents, 35cents] Edge labels: [D, Q]
Your code should follow the Model-View-Controller pattern. In particular, the
FiniteStateMachine class (i.e., the Model) should not perform any input/output. All file access and user interaction should be handled by the driver classes (i.e., the Controllers). 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 either ILLEGAL SEQUENCE or NO SUCH PATH should be displayed.