GATE CSE 2009 | Question: 27

Question

Given the following state table of an FSM with two states $A$ and $B$,one input and one output.

$$\small\begin{array}{|c|c|c|c|c|c|}\hline \textbf{PRESENT} & \textbf{PRESENT} &  & \textbf{Next State } & \textbf{Next State} & \\ \textbf{STATE A} & \textbf{STATE B} & \bf {Input}& \bf {A} & \bf {B} & \bf{Output}\\\hline  \text{0} & \text{0}  & \text{0} & \text{0}  & \text{0}  & \text{1} \\\hline  \text{0} & \text{1}  & \text{0} & \text{1}  & \text{0} & \text{0}\\\hline \text{1} & \text{0}  & \text{0} & \text{0}  & \text{1} & \text{0}\\\hline \text{1} & \text{1}  & \text{0} & \text{1}  & \text{0} & \text{0}\\\hline \text{0} & \text{0}  & \text{1} & \text{0}  & \text{1}  & \text{0} \\\hline \text{0} & \text{1}  & \text{1} & \text{0}  & \text{0} & \text{1} \\\hline \text{1} & \text{0}  & \text{1} & \text{0}  & \text{1}  & \text{1} \\\hline \text{1} & \text{1}  & \text{1} & \text{0}  & \text{0}  & \text{1} \\\hline  \end{array}$$If the initial state is $A=0 ,B=0$ what is the minimum length of  an input string which will take the machine to the state $A=0,B=1$ with $output=1$.

• A. $3$
• B. $4$
• C. $5$
• D. $6$

Comments

Solve using backtracking:

We need 01 and output as  1 
This is only in one case – 10 ( 10 on input 1 gives 01 with output 1)

Now we need 10 (which is possible when the initial state is either 01  or 11 )

Reject 11 as 11 is never next state in any row.

This is only in one case – 01 (01 on input 0 gives 10)

This is only in one case – 00 ( 00 on input 1 gives 01 )

 

So string will be 101 

---

Detailed Video Solution

https://youtu.be/FCmID9qCn5c

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

---

@Mitali gupta Best answer.

Answer 1

backtracking approach.

Answer 2

A simpler approach,

If we simply trace the table, then we can see this sequence will give the required output with input string length as 3.

present state = 00

00 (i/p = 1 , o/p = 0, A=0, B=0) → 01 (i/p = 0 , o/p = 0) → 10 (i/p = 1 , o/p = 1) → 01 .(A=0, B=1 , o/p = 1)

So input string is 101. Length = 3. Option (A).