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

Answer: 3

Key idea: search for the shortest input string (starting from the initial state A=0,B=0) whose final transition arrives at state A=0,B=1 and that arriving transition produces output = 1.

Check strings of increasing length:

1. Length 1: try single-bit inputs. None of the single-bit transitions from the initial state produce arrival at A=0,B=1 together with output = 1 (so no length-1 solution).

2. Length 2: try all two-bit inputs. Exhausting the two-step transitions from the initial state shows that none of them reach A=0,B=1 on the last transition while producing output = 1 (so no length-2 solution).

3. Length 3: a valid shortest input is 1,0,1. The step-by-step transitions are:

   • From initial state A=0,B=0 apply input 1 → follow the table to the next state (intermediate state) and observe the transition output (not 1).

   • From that intermediate state apply input 0 → move to the next intermediate state (transition output not 1).

   • From that intermediate state apply input 1 → the transition arrives at A=0,B=1 and the transition output is 1. Thus the 3-bit string 1,0,1 meets both requirements.

Conclusion: the minimum length of an input string required to take the machine from the initial state A=0,B=0 to state A=0,B=1 with output = 1 is 3, because all shorter strings (length 1 and 2) fail to satisfy both the arrival state and the output condition, and a valid 3-bit witness exists.