GATE CSE 1993 | Question: 6.2

Question

If the state machine described in figure should have a stable state, the restriction on the inputs is given by

• A. $a.b=1$
• B. $a+b=1$
• C. $\bar{a} + \bar{b} =0$
• D. $\overline{a.b}=1$
• E. $\overline{a+b} =1$

Answer 1

If $a = 0$ state changes from $S_1$ to $S_2$ and if $b = 0$ state changes from $S_2$ to $S_1.$

So, $a = 0, b = 0$ is surely not a stable state as then the states will be oscillating. So, the condition for stability is that both $a$ and $b$ should not be $0$ together which is given by $a+b = 1$ or $\overline {ab} = 0.$

Options A and C are equivalent and both ensures stable states albeit by enforcing stricter than required conditions.

Correct Answer: Option B.

Comments

no, i meant that placing above 21 will leave out 18,19,20 year old people.

---

@abhishek29

but here it is just asking the inputs for which it will lead us to the stable state , although the strongest answer here is B , but bcoz of the above reasons A and C can be correct too.

---

I am unable to understand this question, if possible someone please provide a link for any video reference plss.

Answer 2

Let’s take $S_1$ as $0$ and $S_2$ as 1

we can draw the truth table as follows:-

Characteristic Table

a	b	$Q_n$	$Q_{n+1}$
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

 

The states in $Q_n$ column of the above table are $0$ which represent $S_1$ and $1$ which represent $S_2$.

From the above table we can find the following table :-

Derived table

a	b	$Q_{n+1}$
0	0	$\overline{Q}$
0	1	1
1	0	0
1	1	$Q$

For stable state following is the equation:-

                 (if in $S_1$ stay in S1) $\lor$ (if in $S_2$ stay in $S_2$ )

$\implies$ ((if a=1 don’t care about b just remain in $S_1$ ) $\lor$ (a=1 and b=1)) $\lor$ ((if b=1 don’t care about a just                    remain in $S_2$ ) $\lor$ (a=1 and b=1))

$\implies$ (a+a.b)+(b+a.b)

$\implies$ (a(1+b))+(b(a+1))

$\implies$ a+b

so, answer is $(b)\ a+b=1$

Comments

for a= 0, b=0 and Qn = 0, Means current state is S1 and input is a = 0, b= 0. So the next state on iterating this is S1 only. Then why Qn+1 = S2?

---

@neel19 From S1 on, a=0 it is defined that it goes to S2

---

@neel19

I think because of ,In S1 there is no transition present for input b thus only a is considered.