GATE CS 1995 Q2.23 — Sequential Circuits

To find the shortest input sequence that guarantees reaching the state $C$ from an unknown initial state, we must find a sequence of inputs that maps the set of all possible initial states, $S_0 = \{A, B, C, D\}$, to the singleton set $\{C\}$.

Let's trace the state transitions for the input sequences starting with length 1:

• If the input is $0$:
  • $A \xrightarrow{0} B$
  • $B \xrightarrow{0} C$
  • $C \xrightarrow{0} D$
  • $D \xrightarrow{0} C$
  The set of possible states becomes $\{B, C, D\}$ (not guaranteed to be $C$).
• If the input is $1$:
  • $A \xrightarrow{1} D$
  • $B \xrightarrow{1} B$
  • $C \xrightarrow{1} B$
  • $D \xrightarrow{1} B$
  The set of possible states becomes $\{B, D\}$ (not guaranteed to be $C$).

Since no single-input sequence guarantees reaching state $C$, we test the 2-input sequences starting from the state sets obtained above:

Testing Option B: $10$ (Input $1$ followed by $0$)

1. Applying input $1$ to the initial set $\{A, B, C, D\}$ results in the state set $\{B, D\}$.
2. Now, applying input $0$ to the set $\{B, D\}$:
   • $B \xrightarrow{0} C$
   • $D \xrightarrow{0} C$
   The resulting state is guaranteed to be $\{C\}$.

Thus, the sequence $10$ successfully forces the machine into state $C$ regardless of the initial state.

Testing Option A: $01$ (Input $0$ followed by $1$)

1. Applying input $0$ to the initial set $\{A, B, C, D\}$ results in the state set $\{B, C, D\}$.
2. Applying input $1$ to the set $\{B, C, D\}$:
   • $B \xrightarrow{1} B$
   • $C \xrightarrow{1} B$
   • $D \xrightarrow{1} B$
   The resulting state is $\{B\}$, not $C$.

Therefore, the shortest input sequence to reach the final state $C$ is $10$.