GATE 2025 CS (CS1) – Question 59

Digital Logic · Boolean Algebra and Minimization · 2 marks · Numerical answer

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

D and H have identical outputs and next states, so D≡H. B and E have identical next states (D,C), so B≡E. Given B≡E, A and C both go to F on 0 and to B/E on 1, so A≡C. The classes are {A,C}, {B,E}, {D,H}, {F}, {G}, giving 5 states.