GATE CSE 2021 Set 2 | Question: 28

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.

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

• A. $\begin{array}{l} t=s+b \\ y=sb \end{array} \\$
• B. $\begin{array}{l} t=b \\ y=sb \end{array} \\$
• C. $\begin{array}{l} t=b \\ y=s \overline{b} \end{array} \\ $
• D. $\begin{array}{l} t=s+b \\ y=s \overline{b} \end{array}$

Comments

S                     b             y                    t

0                      0           0                     0

0                      1            0                    1

1                     0             0                     0 

1                     1             1                     1

Here S is the Present state 

b is the new incoming bit 

y is the Corresponding output 

t is the  next state 

in state “0” on seeing “0” as i/p we will go to state “0” by giving output as “0”

Only option B matches from this Table.

---

Detailed Video Solution :  https://youtu.be/0t4w9egDrG4

Explanation of Finite State Machines (Mealy, Moore Machines), with ALL GATE Questions’ solution can be found in the following playlist :

https://youtube.com/playlist?list=PLIPZ2_p3RNHjd6P9g6XoUm8E33CsUBqDv

---

Nice one sir @Deepakk Poonia (Dee)

 

 

 

---

👌

Answer 1

In $(a∕b), ‘a\text{’}$ is input and $‘b\text{’}$ is output

Option B is correct. 

Comments

s = current state

t = next state

b = input bit

y = output bit

You are given s and b, you have to give the general formula for t and y.

---

The states are in form of {0, 1}. So we have to give boolean formula for next state and output.

t = b means that the next bit/input is the next state of Mealy Machine

y = sb means output of Mealy machine is current state AND next bit/input

You can just take some random strings and check too.

---

Nonsense Ans! 

Why such 1 liner ans selected as Best!!! 🗿😂

Answer 2

         correct option to question is B

Comments

This should be the best answer.

---

You made so easy to understand ,using digital logic function concept.

---

Best Ans 🔥​​​

Answer 3

We can get Boolean Expressions by following method :-

1.For y:-

Variables(s,b)	b=0	b=1
s=0	0	0
s=1	0	1

Y is 1 only when s=1,b=1 Therefore Y=sb

Explanation for y:- As Y is Output bit for this Machine .We can say Y will produce 1 only when previous bit and current bit =1 ,Therefore as the State 1 means previous input bit was 1.The product of s and b gives y.

 

2.For t :-   As t is for next state which depends only on incoming bit nothing else.Therefore t=b.