Consider a finite state machine (FSM) with one input \(X\) and one output \(f\), represented by the given state transition table. The minimum number of states required to realize this FSM is ________. (Answer in integer)
| Present state | Next state | Output \(f\) | ||
|---|---|---|---|---|
| \(X = 0\) | \(X = 1\) | \(X = 0\) | \(X = 1\) | |
| A | F | B | 0 | 0 |
| B | D | C | 0 | 0 |
| C | F | E | 0 | 0 |
| D | G | A | 1 | 0 |
| E | D | C | 0 | 0 |
| F | F | B | 1 | 1 |
| G | G | H | 0 | 1 |
| H | G | A | 1 | 0 |
Answer
5
Explanation
Minimise by partition refinement. The output depends on the input (a Mealy machine), so first group the states by their output pair for \(X = 0\) and \(X = 1\).
- By outputs: {A, B, C, E} have (0, 0), {D, H} have (1, 0), {F} has (1, 1) and {G} has (0, 1).
- On \(X = 0\), A and C go to F but B and E go to D, and F, D are in different groups. So {A, B, C, E} splits into {A, C} and {B, E}. D and H have identical rows (G, A), so they stay together.
- Next pass: A goes to (F, B) and C to (F, E), with B and E now in one group; B, E and D, H still have identical rows. Nothing splits further.
The groups {A, C}, {B, E}, {D, H}, {F}, {G} give 5 states.
Answer: 5