GATE IT 2006 | Question: 37

Question

For a state machine with the following state diagram the expression for the next state $S^+$ in terms of the current state $S$ and the input variables $x$ and $y$ is

• A. $S^+ = S' . y' + S . x$
• B. $S^+ = S. x . y' + S' . y . x'$
• C. $S^+ = x . y'$
• D. $S^+ = S' . y + S . x'$

Comments

Didn't get the question. Can you please explain

---

Didn't get the que. Plz explain in detail what has to be done exactly

---

This question is a digital logic question actually.
Take S,X,Y and find Sn.  (Characteristic table)
from that you can find the characteristic equation.

---

To save time, we must know how to write equation for Next State directly from state diagram. Refer following video to learn it.

Detailed Video Solution :

https://youtu.be/99NelJegqRY

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

Answer 1

$$\begin{array}{|c|cc|c|} \hline \textbf{Present State}  &&{\textbf {Inputs}}&     \textbf {Next State} \\\hline \textbf{S} & \textbf{x}  & \textbf{y} & \mathbf{S^+} \\\hline 0 & \text{X} & 0&1  \\\hline  0& \text{X} & 1 & 0  \\\hline  1& 0& \text{X}  & 0 \\\hline 1& 1 & \text{X} &1\\\hline \end{array}$$

From above table:

$S^+ = S'y'+Sx$
Correct Answer: $A$

Comments

@sandeep where X is given consider both the Combinations 0 and 1. 
 

1

1

X

means $sxy' + sxy$, Y is X means y and y' both are considered.

---

ThanksBhai.

---

What if

S. x'  +  S'.y

Answer 2

Answer is (A)

For S is 1 only when:      Either (S=1 and x=1) OR (s=0 and y=0)

Therefor  S(next) = S'y'+Sx

Comments

@arjun sir

if s0 is present state then s1 is the next state.

and

when s1 is present state then s0 is next...

then why ans is for s1 only

---

@asu

present value of S in that table has both value 0 and 1 indicating s0 and s1

Answer 3

For those who think A & D both should be the answer. First of all, this is a Digital Logic Design question because they have given options in term of SOP form and we write expressions only for the result obtained =1 in Truth table.

Answer 4

Deriving SOP form is a good approach, but it didn’t clicked for me. I tried this approach. It’s basically elimination method.

Give inputs as S=0 and y=0 to all options, for these inputs S+ should be 1.

(A) S+ = 1

(B) S+ = 0 , eliminated.

(C) S+ = x.(1) = x, here the output depends on x but as (S = 0) state don’t have production for input ‘x’ , that’s why it’s eliminated too.

(D) S+ = 0 , eliminated.

So, option (A) is correct.