The Gateway to Computer Science Excellence

+31 votes

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

- $3$
- $4$
- $5$
- $6$

+37 votes

Best answer

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$

+22 votes

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.

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.

+1 vote

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,251 answers

198,059 comments

104,692 users