search
Log In
21 votes
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

in Theory of Computation
edited by
3.2k views

2 Answers

23 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 


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
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

8 votes
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.......

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

26 votes
5 answers
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
asked Sep 22, 2014 in Theory of Computation Kathleen 2.4k views
21 votes
2 answers
2
2.1k views
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
asked Sep 22, 2014 in Theory of Computation Kathleen 2.1k views
18 votes
2 answers
3
1.4k views
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$
asked Sep 22, 2014 in Theory of Computation Kathleen 1.4k views
30 votes
4 answers
4
3.9k views
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\}$
asked Sep 22, 2014 in Theory of Computation Kathleen 3.9k views
...