GATE CS 2005 Q63 — Regular Expressions and Finite Automata

To understand the behavior of the given finite state machine, let us trace its transitions from the initial state (let's call it $S_0$) when processing a binary number from the Least Significant Bit (LSB) to the Most Significant Bit (MSB).

Standard 2's Complement Algorithm

To find the 2's complement of a binary number starting from the LSB:

• Scan the bits from right to left (LSB to MSB).
• Keep all leading $0$s and the first $1$ unchanged.
• Invert all the remaining bits after the first $1$ (i.e., $0 \to 1$ and $1 \to 0$).

Tracing the State Machine

Let the initial state be $S_0$ and the second state be $S_1$:

1. In state $S_0$ (before encountering the first $1$):
   • An input of $0$ produces an output of $0$ and keeps the machine in $S_0$.
   • An input of $1$ produces an output of $1$ and transitions the machine to $S_1$.
2. In state $S_1$ (after encountering the first $1$):
   • An input of $0$ produces an output of $1$ and keeps the machine in $S_1$.
   • An input of $1$ produces an output of $0$ and keeps the machine in $S_1$.

Example Trace

Consider the input decimal number $6$, which is represented in binary as $110_2$. Reading from LSB to MSB, the input sequence is $0 \to 1 \to 1$:

• Input $0$: Machine is in $S_0$, outputs $0$, remains in $S_0$.
• Input $1$: Machine is in $S_0$, outputs $1$, transitions to $S_1$.
• Input $1$: Machine is in $S_1$, outputs $0$, remains in $S_1$.

The output sequence from LSB to MSB is $0 \to 1 \to 0$, which represents the binary number $010_2$ (decimal $2$).

Since the 2's complement of $6$ ($110_2$) is indeed $2$ ($010_2$), the machine correctly computes the 2's complement of the input binary number.