Official PYQ · 2021Set 2 · Q28Regular Expressions and Finite AutomataMCQ2 marks

GATE CS 2021 Set 2 Q28 — Regular Expressions and Finite Automata

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.

$\begin{array}{ll} \text{Input sequence:} & 00100011000011100 \\ \text{Output sequence:} & 00000001000001100 \end{array}$

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 $s, t, b$ and $y$ respectively.

Assume the initial state of the Mealy machine is $0$ .

What are the Boolean expressions corresponding to $t$ and $y$ in terms of $s$ and $b$ ?

View worked solution

Answer: B

To design the Mealy machine, let us define the meaning of the two states represented by $s \in \{0, 1\}$ :

State $s = 0$ : The previous input bit was $0$ (or we are at the start). We are not currently inside a sequence of consecutive $1$ ’s.
State $s = 1$ : The previous input bit was $1$ . We are currently inside a sequence of consecutive $1$ ’s.

Using this state definition, let us construct the truth table for the next state $t$ and the output $y$ based on the current state $s$ and current input $b$ :

Current State ( $s$ )	Input ( $b$ )	Next State ( $t$ )	Output ( $y$ )
0	0	0	0
0	1	1	0 (first $1$ replaced by $0$ )
1	0	0	0
1	1	1	1 (subsequent $1$ remains $1$ )

From the truth table, we can derive the Boolean expressions:

Next State ( $t$ ): $t$ is $1$ whenever $b = 1$ , regardless of $s$ .
$\therefore t = b$
Output ( $y$ ): $y$ is $1$ only when both $s = 1$ and $b = 1$ .
$\therefore y = sb$

Thus, the correct expressions are $t = b$ and $y = sb$ .

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Regular Expressions and Finite Automata questions

GATE CS 2021 Set 2 Q28 — Regular Expressions and Finite Automata

Related questions