in Theory of Computation edited by
6,546 views
25 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
in Theory of Computation edited by
6.5k views

2 Comments

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.
0
Its a question of mealy machine. where x are input alphabets and y are output alphabets.

In the above question, 1/10 on an arc or arrow can be interpreted  as; 1=input alphabet, 10=output alphabet.
1

Subscribe to GO Classes for GATE CSE 2022

3 Answers

47 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).

edited by
by

7 Comments

reshown 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)
2
it says sum of last two bits, not the sum whole string. So A should be correct.
2

Question should be modified as it says bits not bit...and @Ravi Kaushik no where its mentioned previous 2 bits in the question.

1
Indeed It actually says present and "previous bits". Had me confused as well. Had the "s" no been there then option A would be right. Most probably a typo and everyone who attempted would have gotten marks anyways.
0
It is present bit and previous bit => bits. There's no typo.
0
Here if you take 0111 as input and add each bit from left to right i.e 0+1, 1+1, 1+1, the output you get is 01, 10, and 10 respectively. This output matches the output generated by the mealy machine on the given input. Therefore, we can say that the output represents the sum of the present and previous bits of the input.
0
Exactly the Person who write this question has weak english.
0
1 vote
By taking up a string we may able to figure out the pattern

Let us consider a string 100111
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,0) = (A, 01)
Previous input + Present input = 1+0 = 01
(A,0) = (A, 00)
Previous input + Present input = 0+0 = 00
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,1) = (C, 10)
Previous input + Present input = 1+1 = 10
(C,1) = (C, 10)
Previous input + Present input = 1+1 = 10

option A is correct

option B and C are wrong where they don't produce a correct pattern.
0 votes
What is the output of (C,0)=(A,01)?

2 Comments

Yes
0

kittuD

yep, that's true. Don't consider carry.

0
Answer:

Related questions