The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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

- outputs the sum of the present and the previous bits of the input
- outputs $01$ whenever the input sequence contains $11$
- outputs $00$ whenever the input sequence contains $10$
- none of the above

+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**).

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.8k
- Algorithms 3.3k
- Theory of Computation 4.1k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1.1k
- Others 1.4k
- Admissions 496
- Exam Queries 443
- Tier 1 Placement Questions 19
- Job Queries 59
- Projects 9

37,111 questions

44,694 answers

127,232 comments

43,753 users