GATE CS 2002 Q2.5 — Regular Expressions and Finite Automata

Let us analyze the behavior of the finite state machine by interpreting the states as memory of the previous input bit:

• State $A$: Represents that the previous input bit was $0$ (or we are at the start).
• State $B$: Represents that the previous input bit was $1$.

Now, let's look at the transitions and their outputs (represented as $x/y$, where $x$ is the input and $y$ is the 2-bit binary output):

• From state $A$ (previous bit $= 0$):
  • On input $0$: Transition to $A$, output is $00$ (since $\text{present} + \text{previous} = 0 + 0 = 0$).
  • On input $1$: Transition to $B$, output is $01$ (since $\text{present} + \text{previous} = 1 + 0 = 1$).
• From state $B$ (previous bit $= 1$):
  • On input $0$: Transition to $A$, output is $01$ (since $\text{present} + \text{previous} = 0 + 1 = 1$).
  • On input $1$: Transition to $B$, output is $10$ (since $\text{present} + \text{previous} = 1 + 1 = 2$).

In all cases, the 2-bit output $y$ is the binary representation of the sum of the present input bit and the previous input bit. Thus, option (A) is correct.