How to use the NFA to DFA Converter
- 1. Paste the NFAFirst line lists the symbols, with an e or ε column for ε-moves. Then one line per state.
- 2. List targetsWrite target sets like q0,q1 or {q0,q1}, and - for none. Mark the start with -> and finals with *.
- 3. Read the DFASee ε-closures, each subset step, and the DFA table with new names A, B, C.
How subset construction works
Every NFA has an equivalent DFA whose states are sets of NFA states. The subset (powerset) construction builds only the sets that can be reached:
- The start state of the DFA is the ε-closure of the NFA start state. The ε-closure of a set is every state you can reach using ε-moves alone, including the states themselves.
- For a DFA state T and a symbol a, find move(T, a), the NFA states reachable from T on a. Then take its ε-closure. That set is the next DFA state.
- Repeat for every new set until no new set appears.
- A DFA state is final if it contains at least one NFA final state.
In the worst case an n-state NFA gives 2n DFA states, but most exam NFAs give far fewer.
Worked example: strings ending in 01
The default NFA has q0 → {q0, q1} on 0 and q0 → {q0} on 1, q1 → {q2} on 1, and q2 is final.
- A = {q0}. On 0 it goes to {q0, q1} = B. On 1 it stays at A.
- B = {q0, q1}. On 0 it stays at B. On 1 it goes to {q0, q2} = C.
- C = {q0, q2}. On 0 it goes to B, and on 1 to A. C is final because it holds q2.
The result is a 3-state DFA. For an ε-NFA such as Thompson's construction for (a|b)*abb, the tool gives the five DFA states A to E from the dragon book.
Tips
Name each DFA state by its set first, then give it a letter, so the examiner can check your work. The empty set ∅ is a dead state. Include it if some move leads nowhere, because a DFA needs a move on every symbol. The resulting DFA may not be minimal, so run it through the DFA minimisation tool next. For more practice, try the theory of computation MCQ quiz.
Frequently asked questions
How do I enter ε-moves?
Add a column named e, ε, eps or epsilon in the header and list the ε-targets in that column for each state.
Why does my DFA have a ∅ state?
Some set of states has no move on a symbol. ∅ is the dead state. It loops to itself and is never final.
Is the DFA from subset construction minimal?
Not always. It has only reachable states, but some may be equivalent. Minimise it to get the smallest DFA.
Can an NFA have more than one start state?
Most textbooks use one start state. If yours has several, add a new start state with ε-moves to each of them.