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 $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$?

Question

Which one of the following circuits implements the Boolean function given below?
\[ f(x,y,z) = m_0 + m_1 + m_3 + m_4 + m_5 + m_6, \] where $m_i$ is the $i^{\text{th}}$ minterm.

Answer 1

The problem requires us to design a Mealy machine, a type of finite state machine, to transform an input string of 0s and 1s according to specific rules. The task is to identify the Boolean expressions for the next state $ t $ and the output $ y $ in terms of the current state $ s $ and the input $ b $.

We need to ensure that the circuit replaces the first '1' in any subsequence of consecutive '1's by a '0', while leaving the rest of the '1's unchanged. Let's break down how the Mealy machine processes each bit:

Initially, the machine is in state 0.
If a '0' is encountered in this state, both the state and the output remain '0'.
If a '1' is encountered in state 0, the state changes to 1, and the output becomes '0'. This represents the replacement of the first '1' of the subsequence.
If the machine is already in state 1 and encounters another '1', the machine stays in state 1 but now outputs '1'.
Encountering a '0' in state 1 resets the machine back to state 0, and the output is '0'.

To express this behavior in Boolean terms, observe:

Next State ($ t $): The machine transitions to state 1 upon encountering '1' regardless of current state $ s $. Hence, the expression for $ t $ is simply $ b $.
Output ($ y $): The output '0' occurs either when $ s = 0 $ and $ b = 1 $ or simply when the state switches from 0 to 1 due to '1' input. Thus, when in state 1 and a '1' is encountered ($ sb $), it outputs '1'. Hence, $ y = sb $.

Therefore, the correct Boolean expressions for $ t $ and $ y $ are as follows:

$ t = b $
$ y = sb $

This matches the given correct answer. The options that don't fit the requirement either end up changing states incorrectly or produce incorrect outputs when processed against the test sequence.

Answer 2

The problem requires us to design a Mealy machine, a type of finite state machine, to transform an input string of 0s and 1s according to specific rules. The task is to identify the Boolean expressions for the next state $ t $ and the output $ y $ in terms of the current state $ s $ and the input $ b $.

We need to ensure that the circuit replaces the first '1' in any subsequence of consecutive '1's by a '0', while leaving the rest of the '1's unchanged. Let's break down how the Mealy machine processes each bit:

Initially, the machine is in state 0.
If a '0' is encountered in this state, both the state and the output remain '0'.
If a '1' is encountered in state 0, the state changes to 1, and the output becomes '0'. This represents the replacement of the first '1' of the subsequence.
If the machine is already in state 1 and encounters another '1', the machine stays in state 1 but now outputs '1'.
Encountering a '0' in state 1 resets the machine back to state 0, and the output is '0'.

To express this behavior in Boolean terms, observe:

Next State ($ t $): The machine transitions to state 1 upon encountering '1' regardless of current state $ s $. Hence, the expression for $ t $ is simply $ b $.
Output ($ y $): The output '0' occurs either when $ s = 0 $ and $ b = 1 $ or simply when the state switches from 0 to 1 due to '1' input. Thus, when in state 1 and a '1' is encountered ($ sb $), it outputs '1'. Hence, $ y = sb $.

Therefore, the correct Boolean expressions for $ t $ and $ y $ are as follows:

$ t = b $
$ y = sb $

This matches the given correct answer. The options that don't fit the requirement either end up changing states incorrectly or produce incorrect outputs when processed against the test sequence.

Show Hint

The Correct Option is B

Solution and Explanation

Top Questions on Combinational and Sequential Circuits

Questions Asked in GATE CS exam