Project ForgeGiven a state table of an FSM with two states A and B, one input and one output, with initial state 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? (transitions: (A=0,B=0,in=0)->(A=0,B=0,out=1); (A=0,B=1,in=0)->(A=1,B=0,out=0); (A=1,B=0,in=0)->(A=0,B=1,out=0); (A=1,B=1,in=0)->(A=1,B=0,out=0); (A=0,B=0,in=1)->(A=0,B=1,out=0); (A=0,B=1,in=1)->(A=0,B=0,out=1); (A=1,B=0,in=1)->(A=0,B=1,out=1); (A=1,B=1,in=1)->(A=0,B=0,out=1))
- 3
- B4
- C5
- D6
Explanation
Trace input '1,0,1' from (0,0): on 1 -> (0,1) out=0; on 0 -> (1,0) out=0; on 1 -> (0,1) out=1. This reaches the target state with Output=1 in exactly 3 steps. No length-1 or length-2 input string reaches (A=0,B=1) with Output=1 simultaneously (checked exhaustively), so 3 is minimal.
Source: GATE CS 2009 (2009)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.