GATE 2020 EC Q.39: solution and answer

Official answer: ASource: Official answer key, GATE 2020 EC (IIT Delhi)

1. This is a Mealy machine. Each edge is labelled input/output, so the output depends on both the present state and the present input.

2. Find the only edge whose output is 1. It is $S_4\stackrel{0/1}{\to }{S}_3$, so the output is 1 only when the input is 0 while the machine is in $S_4$.

3. Trace the route from $S_0$ into $S_4$: $S_0\stackrel{0}{\to }{S}_1\stackrel{1}{\to }{S}_2\stackrel{0}{\to }{S}_3\stackrel{1}{\to }{S}_4$. The machine can enter $S_4$ only from $S_3$ on a 1, and it can enter $S_3$ only on a 0 (from $S_2$ or from $S_4$), so the last four inputs before reaching $S_4$ are always $0101$.

4. Add the final input 0 taken from $S_4$. The sequence that makes the output 1 is $01010$, which is 01010.

5. Check the other options by tracing each one from $S_0$. (B) 01011: $S_0\to S_1\to S_2\to S_3\to S_4$, then the input 1 takes $S_4\stackrel{1/0}{\to }{S}_0$, so the output is 0.

6. (C) 01110: $S_0\to S_1\to S_2$, then the input 1 takes $S_2\stackrel{1/0}{\to }{S}_0$, the next 1 keeps it in $S_0$ (self-loop), and the final 0 takes it to $S_1$. The output is 0 throughout.

7. (D) 01001: $S_0\to S_1\to S_2\to S_3$, then the input 0 takes $S_3\stackrel{0/0}{\to }{S}_1$ and the input 1 takes $S_1\stackrel{1/0}{\to }{S}_2$. The output is 0 throughout.

8. After a detection the machine goes to $S_3$, the state that means "010 received". The last three bits of 01010 are 010, so this is an overlapping detector. For example, 0101010 gives output 1 at bit 5 and again at bit 7.