Note: no late submissions will be accepted for this assignment.
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.
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.
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
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