GATE CS 2025 Set 1 Q.59: Sequential Circuits, Counters and Registers

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

Your answer

Official answer and solution

Official answer: 5
From: Official GATE 2025 answer key

Solution

Apply Moore/Mealy partition refinement starting from the output equivalence classes.

Initial partition $P_0$ by output $(f|_{X=0}, f|_{X=1})$ :
- Output (0, 0): $\{A, B, C, E\}$
- Output (1, 0): $\{D, H\}$
- Output (1, 1): $\{F\}$
- Output (0, 1): $\{G\}$
Refine $\{D, H\}$ :
- Both $D$ and $H$ transition to $(G, A)$ , so $D \equiv H$ .
Refine $\{A, B, C, E\}$ :
- $B$ and $E$ have the exact same next-state transitions $(D, C)$ , so $B \equiv E$ .
- $A$ transitions to $(F, B)$ and $C$ transitions to $(F, E)$ . Since $B \equiv E$ , $A$ and $C$ transition to equivalent next states for all inputs, while differing from $B$ and $E$ on $X = 0$ ( $F \not\equiv D$ ). Thus $\{A, B, C, E\}$ splits into $\{A, C\}$ and $\{B, E\}$ .

The final equivalence classes are $\{A, C\}, \{B, E\}, \{D, H\}, \{F\}, \{G\}$ , giving a minimum of 5 states.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 1 (CS1)
Question: 59 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source