GATE CSE 2025 Session 1 Q59: Minimum states of an FSM from its state table

Digital Logic
2 marks
NAT
No negative marking

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

Try it: numerical answer: type the value

Your answer

Numerical answer. No negative marking.

Show answer and explanation

Answer: 5 (official GATE 2025 final answer key)

Concept used: State minimisation by partitioning: states are equivalent if they give the same outputs and move to equivalent states.

First step: Group by output pattern: {A, B, C, E} give 00, {D, H} give 10, F gives 11, G gives 01; then split groups whose next states fall in different groups.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 Session 1 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key

PracticePractise Digital Logic questions →Full paperAll GATE CSE 2025 Session 1 questions →

GATE CSE 2025 Session 1 Q59: Minimum states of an FSM from its state table

Question

Full step-by-step solution

More Digital Logic PYQs