What is the minimum number of states required to the finite automaton…
2021
What is the minimum number of states required to the finite automaton equivalent to the transition diagram given below?
- A.
3
- B.
4
- C.
5
- D.
6
Attempted by 148 students.
Show answer & explanation
Correct answer: C
Answer: 5 states
Reasoning (sketch): convert the given transition diagram to an equivalent deterministic automaton using the subset construction, then minimize.
Start subset: {a}.
From the start subset, follow transitions on 0 and 1 to get new subsets (for example {b,c} on 0 and {f} on 1).
Continue expanding reachable subsets until no new subsets appear. The distinct reachable DFA states produced by this construction are five in number (the start subset and four other reachable subsets).
Minimization: check pairwise equivalence of the reachable DFA states. Because the subsets have different acceptance behaviour (some contain accepting NFA states and others do not) and produce different next-subset patterns, none of the five reachable states can be merged further.
Conclusion: the minimal DFA equivalent to the given transition diagram has 5 states.
A video solution is available for this question — log in and enroll to watch it.