As we discussed in class, a Finite State Machine (FSM) 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 FSM that defines the rules for spacing within a legal Morse code message.

For this assignment, you will define a series of classes that simulate finite state machines. Each version will need to be able to read in the definition of a FSM from a file and process a sequence of steps from a start state to determine the final state. In all three versions, the amount of work required to process a sequence of N steps should be O(N). This means that you will have to be careful in your design of data structures to ensure linear performance.

FSM1 Simulator - Integer States & Binary Edges (70%)

The first version of your FSM simulator will assume that the states are labeled with integers in a range 1 to N and edges are labeled with 0 or 1. A FSM will be defined in a file where the first line gives the number of states and subsequent lines are of the form v1 e v2, where v1 and v2 are state labels and e is an edge label. For example, the FSM on the left would be represented by the text file on the right:

2 1 0 2 1 1 1 2 0 1 2 1 2

You should define a class named FSM1 that models a FSM of this type and is able to determine the state of the machine after a series of steps. You should also define a class named FSM1Driver that prompts the user for the name of a FSM file and then repeatedly prompts for a start state and a sequence of steps (edge labels, separated by whitespace) and displays the resulting final state. For example:

Enter FSM file: even1.txt

Enter a start state (-1 to end): 1
Enter a step sequence (separated with whitespace): 0 1 1 0 0 1
End state: 2

Enter another start state (-1 to end): 1
Enter a step sequence (separated with whitespace): 0 1 0
End state: 1

Enter another start state (-1 to end): -1
DONE

In the above FSM, each state has two outgoing edges (labeled 0 and 1). This may not always be the case, however. For example, a state in a different FSM might have an edge labeled 0 coming out of it but no edge labeled 1. If a sequence of steps ever attempts to use a nonexistent edge, the message ILLEGAL SEQUENCE should be displayed in place of the final state.

FSM2 Simulator - Text States & Binary Edges (15%)

For the next version of your FSM simulator, you should allow for text labels on the states as opposed to numbers. For example, in the FSM shown above, the labels "even" and "odd" would be more illustrative as to their significance.

2 even 0 odd even 1 even odd 0 even odd 1 odd

You will need to define new versions of your classes, call them FSM2 and FSM2Driver that utilize this new format.

Enter FSM file: even2.txt

Enter a start state (* to end): even
Enter a step sequence (separated with whitespace): 0 1 1 0 0 1
End state: odd

Enter another start state (* to end): even
Enter a step sequence (separated with whitespace): 0 1 0
End state: even

Enter another start state (* to end): *
DONE

FSM3 Simulator - Text States & Text Edges (15%)

2 4 inWord . inWord inWord - inWord inWord _ betweenWords inWord __ betweenWords betweenWords . inWord betweenWords - inWord

Using this new file format, FSM3 and FSM3Driver would produce the following:

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