What is the minimum number of states to realize the FSM in GATE CS 2025 Q59?

Using the partition refinement method, states B and E are equivalent (same output, same next-state group behavior). All other 6 state groups are distinguishable, giving a minimum of 6 states. Please verify with the official GATE 2025 answer key.

How do you minimize an FSM using the partition refinement method?

First, partition states by their output values. Then iteratively split partitions: two states in the same partition are split apart if their next states on any input fall into different partitions. Repeat until no more splits occur. The number of final partitions is the minimum state count.

Which states are equivalent in the GATE CS 2025 Q59 FSM?

States B and E are equivalent. Both have output (0,0), B goes to (D,C) and E goes to (D,C) on inputs X=0 and X=1 respectively, mapping to the same partition groups at every refinement step.

What is the implication table method for FSM minimization?

The implication table method fills a triangular table for all state pairs. A pair is marked distinguishable if they have different outputs. Then, pairs whose implied next-state pairs are distinguishable are also marked. Unmarked pairs at the end are equivalent and can be merged.

FSM State Minimization: Minimum States from 8-State Table

Computer Sciences > GATE 2025 SET-1 > Finite State Machines

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	E	F	0	0
D	G	A	1	0
E	D	C	0	0
F	F	B	1	1
G	H	G	1	0
H	A	G	1	0

Correct : 6

To minimize this FSM, we apply the partition refinement method.
First, group states by their output pairs (O_X=0, O_X=1):
• Output (0,0): A, B, C, E
• Output (1,0): D, G, H
• Output (1,1): F — unique, cannot merge with anyone
Refining {A, B, C, E} by checking where their next states fall:
• A → (F, B): goes to {F} and {A,B,C,E}
• B → (D, C): goes to {D,G,H} and {A,B,C,E}
• C → (E, F): goes to {A,B,C,E} and {F}
• E → (D, C): goes to {D,G,H} and {A,B,C,E}
B and E have identical next-state group behavior → B ≡ E. A and C are distinct from each other and from B/E.
Refining {D, G, H}:
• D → (G, A): X=0 goes to {G}, X=1 goes to {A}
• G → (H, G): X=0 goes to {H}, X=1 goes to {G}
• H → (A, G): X=0 goes to {A}, X=1 goes to {G}
D, G, H all have different X=0 destinations → all three are distinguishable.
Final partitions: {A}, {B,E}, {C}, {D}, {F}, {G}, {H} = 6 minimum states.

Similar Questions

Related Topics

Similar Questions

Related Topics

Question Options

Sign in to ExamPrev