State Minimization


For this exercise, you will fill in the missing bits of a state minimization program. The skeleton code is available here. The program consists of the following source files (more details can be found in comments in the files themselves):


On departmental Linux machines, you can compile the minimizer by typing:

javac *.java
at the command line, after untaring the package.

The program expects it's input on standard input, so if you have a state machine specification in file "fsm.txt", you can run the minimizer on it by typing:

java StateMin < fsm.txt
at the command line.

The format of the FSM specifications is:

Moore/Mealy NumStates NumInputPatterns NumOutputPatterns [Row]+
where a Row is
[NextState]+ [Output]+
NumStates, NumInputPatterns, NumOutputPatterns, NextState and Output are all just integers. Some examples will help:

This FSM is an example where three states are merged into one.

Moore 4 2 2
3 1   1
3 2   1
3 0   1
2 0   0
Each row defines a state. The states are implicitly numbered [0..NumStates-1]. The first two columns here are the next states for input conditions 0 and 1, respectively. The last column is the output.

The minimized state machine looks like:

This would be written as:
Moore 2 2 2
1 0   1
0 0   0

This FSM is an example of a Mealy machine.

Mealy 4 2 2
0 3   0 1
1 3   0 0
2 3   0 1
2 1   0 0
In this case, there are two output columns

The minimized state machine looks like:

This would be written as:
Mealy 3 2 2
0 2   0 1
1 2   0 0
0 1   0 0

This FSM is an example where it takes two iterations through the implication chart to cross out all the cells that need to be crossed out.

Moore 7 2 2
1 2   0
3 4   1
4 3   1
5 6   0
6 5   0
5 5   1
6 6   0
There is no minimization that can be done to this FSM.

The last example has three input patterns, instead of two.

Moore 3 3 2
1 0 2   1
0 1 2   0
0 1 2   0
In this case, there are three next state columns

The minimized state machine looks like:

This would be written as:
Moore 2 3 2
1 0 1   1
0 1 1   0

What You Have to Do

I have removed three critical bits of code from my working version of the state machine minimizer, all in

In each file, I have marked the number of lines that my solution takes up with comment characters (//) at the beginning of the line (note that for the sake of clarity of code and efficiency of implementation, the solution is not necessarily the most compact code possible). Your solution does not need to have exactly that many lines, but it should be a rough guideline for how much code you need to write.

Also, you must hand in one example state machine that you think is particularly complicated. Think about weird special cases that the minimizer has to handle, and make a state machine that exercises those cases. This will make up a very small part of your programming assignment grade. Please write your FSM in text format that the minimizer recognizes and submit it with your code. (There is no need to package your files together with zip or tar.)


Use the Catalyst tool "Collect It" to submit your programming assignment.