The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 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 (59.5k points)
edited by | 1.3k views
I am unable to understand ( or rather Interpret ) the question, what is arc label? what is the significance of x and y here?? Appreciate your time, Thanks.

1 Answer

+28 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 Boss (15.1k points)
edited 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

37,111 questions
44,694 answers
43,753 users