State Minimization

Overview

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):

StateMin.java: This class contains the main method and code for parsing state machines written in a format described below.
StateTable.java: This class represents a state machine as an array of StateTableRows.
StateTableRow.java: This class is a simple container for the information in a row of a state table (i.e., next state and output information).
ImplicationChart.java: This class defines the representation of an implication chart, and has methods for finding pairs of states to merge and building the resulting state table.

Interface

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 ImplicantionChart.java:

markOutputMismatches: This method marks all pairs of states as incompatible that do not share the same output (or vector of outputs, in the Mealy case).
markNextStateMismatches: This method iteratively marks pairs of states as incompatible, if for some input they transition to pair of incompatible states.
buildNewStateTable: This method merges all pairs of states that the minimization algorithm did not mark as incompatible, and produces a new state table.

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.)

Turn-in

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