GATE 2025 CS (CS1) – Question 59
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 X=0 | Next state X=1 | Output f X=0 | Output f 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
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 5
Explanation
Two states can be merged iff they have the same outputs and their next states are equivalent. Group by outputs $(f_{X=0},f_{X=1})$:
- $\{A,B,C,E\}$: $(0,0)$; $\{D,H\}$: $(1,0)$; $\{F\}$: $(1,1)$; $\{G\}$: $(0,1)$.
Refine using next states:
- $D$ and $H$ both go to $(G,A)$: equivalent.
- Among $A,B,C,E$: $A\to(F,B)$, $C\to(F,E)$ go to $F$ on 0; $B\to(D,C)$, $E\to(D,C)$ go to $D$ on 0. So $\{A,C\}$ and $\{B,E\}$ must be separate classes.
- $A$ and $C$: they go to $F$ on 0 and to $B$ and $E$ on 1; since $B\equiv E$, $A\equiv C$.
Equivalence classes: $\{A,C\},\{B,E\},\{D,H\},\{F\},\{G\}$ $\Rightarrow$ minimum **5** states.