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

From above table, we look at next state part

Whenever we reach state $00$ we get output $1$ [at row $1$,row $6$, row $8$], so we have state 00 with output 1

When we reach at state $01$, we get output $0$ [at row $3$, row $5$] and output $1$ [row $7$], so we have two state 01 with output 0, 01 with output 1.

When we reach at state $10$, we get output we get output $0$ [at row $2$, row $4$], so we have state 10 with output 0.

We don't reach at state $11$ [$11$ is not there in next state part], but we have state 11 with don't know (N) output.

If we draw the Moore Machine for above FSM [ from the table: present state x input symbol -> next state ]

 

It is clear from FSM from state $00$ to reach state $01$ with output $1$ i.e, $01/1$ with need minimum length input 101

Minimum length of input $=$ length of $101$. That is 3.

Correct Answer: $A$

Comments

The basic idea here is whenever we are trying to find shortest path from a node A to node B, we will never take cycle (loops) inbetween...

---

Sir I solved this question by looking at it as a mealy machine, not moore. Is that wrong approach?

---

How do we know that the two states A and B have to be considered as a single state in Moore machine?

---

@Queenia .. No problem , Mealy and Moore are equivalent

@Matrix, You need to go though sequential logic circuits. It is just as 2 variable makes 4 different combinations

Answer 2

A = 0, B = 1, Output = 1 is given only by the second last transition in the table. So, we can go back from here.

Here, the previous state is A = 1, B = 0. So, see which state gives next state as this. (1 char is gone here)

The second and fourth transitions in the table gives this as next state. Previous state of second transition is  A = 0 and B = 1. Lets consider this first (2 chars gone).
The fifth transition gives A = 0 and B = 1 from A = 0, B = 0 which is our given initial state (3 chars). So, we needn't check any other possibility as 3 must be the minimum length of the input string.

Comments

great explanation👍

Answer 3

Mealy Machine Approach.

Answer 4

Consider the below given FSM (represented as graph)

From the given FSM we can clearly see that, if we start from initial state (00) and follow the input “101” 

{state 00, 1} -> state “01” , output 0,
{state 01, 0} -> state “10” , output 0,
{state 10, 1} -> state “01” , output 1,
Hence it require an input string of minimum length 3, which will take the machine to the state A=0, B=1 with Output = 1.

Answer 5

backtracking approach.

Answer 6

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).