GATE CSE 2021 Set 2 Q38: Two-state Mealy machine that clears the first 1 of each run
- Digital Logic
- 2 marks
- MCQ
- −2/3 if wrong
Question
Suppose we want to design a synchronous circuit that processes a string of 0's and 1's. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1's by a 0. Consider the following example.
Input sequence: 00100011000011100
Output sequence: 00000001000001100
A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input.
The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables , , and respectively.
Assume the initial state of the Mealy machine is 0.
What are the Boolean expressions corresponding to and in terms of and ?
Try it: multiple choice: exactly one correct option
Show answer and explanation
Answer: B (official GATE 2021 final answer key)
Concept used: The state only needs to remember whether the previous input bit was 1.
First step: Let the state be the previous bit, so ; the output is 1 only when the current bit is 1 and the previous bit was also 1.
Full step-by-step solution
Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.
Share this question
Source: official GATE 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key
More Digital Logic PYQs
- 2026 Session 1 · Q21Expressions equivalent to (P̄ + Q) ⊕ (P̄Q)
- 2026 Session 1 · Q22Overflow with 8-bit sign-magnitude operands
- 2026 Session 1 · Q37D flip-flop inputs for a 2-bit saturating up/down counter
- 2026 Session 1 · Q48Minimal SOP forms of Σm(1,2,3,4,5,7,10,12,13,14)
- 2026 Session 2 · Q16Which identity is not a law of Boolean algebra
- 2026 Session 2 · Q28Overflow in 4-bit two's complement additions