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

+29 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.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,713 questions

46,750 answers

140,552 comments

58,380 users