The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 votes

The finite state machine described by the following state diagram with A as starting state, where an arc label is and x stands for 1-bit input and y stands for 2-bit output


  1. outputs the sum of the present and the previous bits of the input
  2. outputs 01 whenever the input sequence contains 11
  3. outputs 00 whenever the input sequence contains 10
  4. none of the above
asked in Theory of Computation by Veteran (68.9k points)
retagged by | 1k views

This might help ....

1 Answer

+27 votes
Best answer

answer should be option (A).

option (B) and (C)  are clearly wrong . it says input 11 then o/p 01 and i/p 10 then o/p 00 but here at single bit o/p is 2 bit sequence 

now for option (a) we can trace out .. suppose string is 0111  

at A---0---> A----1---> B--1-->C---1-->C

O/P            00            01       10         10  

we can see here at (A,0)---> (A,00) which sum of 0+0=00, (previous i/p bit + present i/p bit)

(A,1)--->(B,01) which is sum of 0+1= 1=01,

(B.1)--->(C,10) which is sum of 1+1= (previous i/p bit + present i/p bit)=10 ,

(C,1)---> (C,10) which is sum of 1+1=10

so answer should be (A).

answered by Veteran (14k points)
selected by
Then why output of 101 in not 10???

And as per statement A it says sum of present and "previous bits" (not bit).

So according to me answer should be D)
it says sum of last two bits, not the sum whole string. So A should be correct.

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

32,694 questions
39,293 answers
36,702 users