Given a Non-deterministic Finite Automation (NFA) with states p and r as…
2013
Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below. The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
- A.
5
- B.
4
- C.
3
- D.
2
Attempted by 37 students.
Show answer & explanation
Correct answer: B
The NFA has initial state p and final state r. Subset construction yields states {p}, {}, {q}, {r}, {s}.
Minimizing shows {q} and {s} are equivalent because they behave identically regarding final states. Merging them leaves 4 distinct states: {p}, {}, {q,s}, and {r}.
A video solution is available for this question — log in and enroll to watch it.