GATE CS 2003 Q44 — Sequential Circuits

Let $d_k = z_k - n_k$ represent the difference between the number of $0$s and $1$s after receiving $k$ bits of input. Initially, at $k=0$, we have $d_0 = 0$.

At any step, receiving a $0$ increases $d_k$ by $1$, and receiving a $1$ decreases $d_k$ by $1$. The circuit tracks this difference until it reaches $+2$ or $-2$. We can define the states based on the value of $d_k$:

• State $S_0$ ($d_k = 0$): The initial state. Output is $00$.
• State $S_1$ ($d_k = +1$): Output is $00$.
• State $S_2$ ($d_k = -1$): Output is $00$.
• State $S_3$ ($d_k = +2$): An absorbing state. Once reached, the output becomes $10$ and remains $10$ forever.
• State $S_4$ ($d_k = -2$): An absorbing state. Once reached, the output becomes $01$ and remains $01$ forever.

None of these $5$ states can be merged because:

• $S_3$ and $S_4$ have different outputs ($10$ vs $01$).
• $S_0, S_1,$ and $S_2$ have different transitions. For example, on input $0$, $S_1$ transitions to $S_3$ (output $10$), whereas $S_0$ transitions to $S_1$ (output $00$).

Thus, the minimum number of states required is $5$.