GATE2025_CS1_Q59

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	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

✅ Final Answer:

The correct answer is 5.

🔹 Short Answer:

The state minimization is performed using the state partitioning method. Initially, states are partitioned based on their output behavior. Then, partitions are iteratively refined based on the next state transitions. The process concludes when no more partitions can be split. The final partitions are {A, C}, {B, E}, {D, H}, {F}, {G}. This results in 5 equivalent states, so the minimum number of states required is 5.

🔸 Long Answer:

To find the minimum number of states, we need to perform state minimization on the given FSM. We will use the partitioning method, which groups states that are equivalent.

Step 1: 0-Equivalence Partitioning (Based on Output)

We partition the states into groups where all states in a group have the same output for every input.
The output vector for a state is `(output for X=0, output for X=1)`.

• Output (0, 0): {A, B, C, E}
• Output (1, 0): {D, H}
• Output (1, 1): {F}
• Output (0, 1): {G}

So, our initial partition (P₀) is: P₀ = { (A, B, C, E), (D, H), (F), (G) }

Step 2: 1-Equivalence Partitioning (Refining P₀)

Now, we check if states within each group of P₀ are equivalent with respect to their next states. Two states are 1-equivalent if, for every input, their next states belong to the same group in P₀.

Let's examine the group (A, B, C, E):

State	Next(X=0)	Next(X=1)	Group of Next(X=0)	Group of Next(X=1)
A	F	B	(F)	(A,B,C,E)
B	D	C	(D,H)	(A,B,C,E)
C	F	E	(F)	(A,B,C,E)
E	D	C	(D,H)	(A,B,C,E)

From the table, we see:

• A and C have next state transitions to groups `(F)` and `(A,B,C,E)`.
• B and E have next state transitions to groups `(D,H)` and `(A,B,C,E)`.

Since their transition patterns are different, we must split the group (A, B, C, E) into (A, C) and (B, E).

Now let's examine the group (D, H):

State	Next(X=0)	Next(X=1)	Group of Next(X=0)	Group of Next(X=1)
D	G	A	(G)	(A,B,C,E)
H	G	A	(G)	(A,B,C,E)

Both D and H transition to group `(G)` on X=0 and to group `(A,B,C,E)` on X=1. They are 1-equivalent, so the group (D, H) does not split.

Our new partition (P₁) is: P₁ = { (A, C), (B, E), (D, H), (F), (G) }

Step 3: 2-Equivalence Partitioning (Refining P₁)

We repeat the process for the new partition P₁.

Examine (A, C):

State	Next(X=0)	Next(X=1)	Group of Next(X=0) in P1	Group of Next(X=1) in P1
A	F	B	(F)	(B,E)
C	F	E	(F)	(B,E)

A and C are equivalent. No split.

Examine (B, E):

State	Next(X=0)	Next(X=1)	Group of Next(X=0) in P1	Group of Next(X=1) in P1
B	D	C	(D,H)	(A,C)
E	D	C	(D,H)	(A,C)

B and E are equivalent. No split.

Since no groups were split in this iteration, the process has converged. The final partition P₂ is the same as P₁.

Final Partition = { (A, C), (B, E), (D, H), (F), (G) }

Step 4: Count the Minimum Number of States

Each group in the final partition represents a single state in the minimized FSM. Counting the number of groups gives us the minimum number of states required.

There are 5 groups in the final partition. Therefore, the minimum number of states is 5.

Bibliography:
- Kohavi, Z., & Jha, N. K. (2009). Switching and Finite Automata Theory. Cambridge University Press. (Chapter 10: State Minimization).
- Mano, M. M., & Ciletti, M. D. (2012). Digital Design: With an Introduction to the Verilog HDL. Pearson. (Chapter 5: Synchronous Sequential Logic).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.