# GATE2005-63

3.2k views

The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which of the following is TRUE?

1. It computes $1$’s complement of the input number

2. It computes $2$’s complement of the input number

3. It increments the input number

4. it decrements the input number

edited

For any binary no, FSM read input from LSB and remain unchanged till first $1$, and it complement after that

$\mathbf{100} \rightarrow \mathbf{100}$     $[1$'s complement of $100 + 1 = 011+ 1 = 100 = 2$'s complement of $100]$

$0\mathbf{10} \rightarrow 1\mathbf{10}$     $[1$'s complement of $010 + 1 = 101 + 1 = 110 = 2$'s complement of $010]$

$1010\mathbf{100} \rightarrow 0101\mathbf{100}$    $[1$'s complement of $1010100 + 1 = 0101011+ 1 = 0101100]$

Note : Underline part is unchanged (till first $1$ from lsb) then $0$'s changed to $1$'s and $1$'s changed to $0$'s

edited
1
@Praveen sir why to read input from LSB and remain unchanged till first 1 ? not getting the logic

would you explain in details with examples
5

It's mentioned in the question to read input from LSB and the bits doesn't change until the 1st 1 from LSB because when you calculate 2's complement for example

10110 --> 01001 ---> then when you'll add 1 to this number it will carry over till it finds 0 which automatically makes the same as input

01001 + 1 = 01010

10 is the same as input and all other bits are inverted

B.

the given above is a mealy machine for finding 2's complement.
0
Can you please explain how this F.A will work on input 100....

I am getting 001

Starting from L.S.B ....input 0 we will get output as 0, input 0 we will get output 0, input 1 we will get output as 1

Thus the final string which is generated is 001

But the 2's complement of 100 is 100.......

0

If your input is 100(1 being MSB and 0 being LSB) then input for FA is in the order 001(LSB first)

q0 --0--> q0 --0--> q0 --1-->q1

o/p:0             0             1

LSB                      MSB

input : 100(1 being MSB and 0 being LSB)

output : 100(1 being MSB and 0 being LSB)

## Related questions

1
2.4k views
Consider the languages: $L_1 = \left\{ww^R \mid w \in \{0, 1\}^* \right\}$ $L_2 = \left\{w\text{#}w^R \mid w \in \{0, 1\}^* \right\}$, where $\text{#}$ is a special symbol $L_3 = \left\{ww \mid w \in \{0, 1\}^* \right\}$ Which one of the following is TRUE? $L_1$ is a deterministic CFL $L_2$ is a deterministic CFL $L_3$ is a CFL, but not a deterministic CFL $L_3$ is a deterministic CFL
Let $L_1$ be a recursive language, and let $L_2$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE? $L_1$' is recursive and $L_2$' is recursively enumerable $L_1$' is recursive and $L_2$' is not recursively enumerable $L_1$' and $L_2$' are recursively enumerable $L_1$' is recursively enumerable and $L_2$' is recursive
Let $N_f$ and $N_p$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let $D_f$ and $D_p$ denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata respectively. Which one ... $D_f = N_f \text{ and } D_p = N_p$ $D_f =N_f \text{ and } D_p \subset N_p$
Consider the machine $M$: The language recognized by $M$ is: $\left\{ w \in \{a, b\}^* \text{ | every a in$w$is followed by exactly two$b$'s} \right\}$ $\left\{w \in \{a, b\}^* \text{ | every a in$w$is followed by at least two$b$'s} \right\}$ ... $contains the substring$abb$'} \right\}$ $\left\{w \in \{a, b\}^* \text{ |$w$does not contain$aa$' as a substring} \right\}$