Equivalent States
- Two states of an FSM are equivalent if for each input they produce, the same output and their states are identical
- To find equivalent states systematically, we use an implication chart
Implication Chart Method
- Identify equivalent states → minimise number of states
- Use implication table → looks at pairs of states and identifies which states have to be equivalent if this pair is to be equivalent
- Use the table to hold information about each pair
We start with a blank chart:
- Cross out incompatible states based on outputs
- For each pair that has any difference in the output, place X in the table to indicate that the pair of states cannot be equivalent
- Then, write in implied state pairs in the remaining squares
- Remaining pairs have the same output, so they could possibly be equivalent, but that is only if their “next states” are equivalent
- For example, states S0 and S4 would be equivalent (S0 ≡ S4) if it also turns out that S3 ≡ S5 (for inputs XY=11)
- Now for each square, test if each statement can be equivalent
- If any of the statements are already crossed, then we can immediately rule out the chosen square
e.g. in the above example, S3-S4 is already crossed,
S2-S0 is not equivalent
- If any of the statements are already crossed, then we can immediately rule out the chosen square
- For the above example:
- S0==S4 and S3==S5
New State Table:
Minimising Incompletely Specified FSMs
- Equivalence of states is transitive when machine is fully specified
i.e. no don’t cares - But its not transitive when don’t cares are present