GATE CS 1996 Q2.23 — Sequential Circuits

To find the number of states in the minimized machine, we use the state equivalence partitioning method.

Step 1: $0$-equivalence partition ($P_0$)

We group the states based on their outputs for each input combination $(x = 0, x = 1)$:

• State $A$: outputs $(0, 1)$
• State $B$: outputs $(0, 1)$
• State $C$: outputs $(0, 1)$
• State $D$: outputs $(1, 1)$

Since $A, B,$ and $C$ have the same output behavior, and $D$ has a different output behavior, we partition them as:

Step 2: $1$-equivalence partition ($P_1$)

We check if the states in the group $\{A, B, C\}$ transition to the same groups under inputs $0$ and $1$:

• For input $0$:
  • $A \to D$ (which belongs to the group $\{D\}$)
  • $B \to A$ (which belongs to the group $\{A, B, C\}$)
  • $C \to A$ (which belongs to the group $\{A, B, C\}$)

Since $A$ transitions to a different group than $B$ and $C$ on input $0$, state $A$ must be split from the group.

Now we check $B$ and $C$:

• For input $0$: both $B$ and $C$ transition to $A$ (same group).
• For input $1$: $B \to C$ and $C \to B$ (both belong to the group $\{A, B, C\}$).

Thus, $B$ and $C$ remain equivalent. The new partition is:

Step 3: $2$-equivalence partition ($P_2$)

We check the remaining multi-state group $\{B, C\}$ with respect to the partition $P_1$:

• For input $0$: both $B$ and $C$ transition to $A$ (which belongs to the block $\{A\}$).
• For input $1$: $B \to C$ and $C \to B$ (both belong to the block $\{B, C\}$).

Since their transitions fall into the same blocks of $P_1$, $B$ and $C$ remain equivalent:

Since $P_2 = P_1$, the partition has stabilized. The minimized states are:

1. State $A$
2. Equivalent state $BC$
3. State $D$

Therefore, the number of states in the minimized machine is $3$.