GATE CS 2018 Q22 — Sequential Circuits

Let the state of the sequential circuit be represented by $(Q_1, Q_0)$, where $Q_1$ and $Q_0$ are the outputs of the first and second D flip-flops respectively.

From the circuit diagram, the input equations to the flip-flops are:

Since the next state of a D flip-flop is equal to its input ($Q^+ = D$), the next-state equations are:

For a state $(Q_1, Q_0)$ to transition back to itself, we require $Q_1^+ = Q_1$ and $Q_0^+ = Q_0$ for some input value $\text{in} \in \{0, 1\}$:

1. First Condition: $$Q_1^+ = Q_1 \implies Q_1 \oplus Q_0 = Q_1 \implies Q_0 = 0$$This restricts the candidate states to those where $Q_0 = 0$.
2. Second Condition: $$Q_0^+ = Q_0 \implies Q_1 \oplus \text{in} = Q_0$$Substituting $Q_0 = 0$ gives:$$Q_1 \oplus \text{in} = 0 \implies \text{in} = Q_1$$

Thus, for any state with $Q_0 = 0$, we can choose $\text{in} = Q_1$ to transition back to the same state:

• State $(0, 0)$ transitions to itself when $\text{in} = 0$.
• State $(1, 0)$ transitions to itself when $\text{in} = 1$.

For states with $Q_0 = 1$, we get $Q_1^+ = \overline{Q_1} \neq Q_1$, making a self-transition impossible.

Hence, there are exactly 2 such states.