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 betweenLetters and inLetter).

Part1: FinteStateMachine (70%)

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.

Part 2: PathTracer (20%)

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

Part 3: PathFinder (10%)

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]

Additional Requirements

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.