What is the minimum length of a string that can take the automaton from the…
2022
What is the minimum length of a string that can take the automaton from the start state to the final state?
- A.
0
- B.
1
- C.
2
- D.
3
Attempted by 120 students.
Show answer & explanation
Correct answer: B
Answer: 1
Reasoning:
Compute the ε-closure of the start state q0: q0 has an ε-transition to q1, and q1 has an ε-transition to q2. So q2 is reachable from q0 without consuming any input.
From q2, on the symbol 'a' there is a transition to q3 (the final state). Therefore reading a single 'a' after the ε-moves reaches the final state.
Conclusion: The minimum length of a string that reaches the final state is 1.
A video solution is available for this question — log in and enroll to watch it.