The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.4k 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

asked in Theory of Computation by Veteran (59.5k points)
edited by | 1.4k views

2 Answers

+18 votes
Best answer

Answer is option B.

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 

answered by Veteran (55k points)
edited by
+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
+2

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

+7 votes
B.

the given above is a mealy machine for finding 2's complement.
answered by Boss (19.7k points)
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.......

Please explain....
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)

Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,039 questions
45,533 answers
131,815 comments
48,848 users