Convert an NFA to a DFA online
This NFA to DFA converter uses subset construction to turn a nondeterministic finite automaton into a deterministic one that recognizes the same language. Draw states and transitions, mark the start and accepting states, then convert. The output includes a transition table with the original NFA subsets and a graph whose states are labelled A0, A1 and so on.
Use the table to check a formal-languages assignment or understand why one DFA state may represent several simultaneously active NFA states. The visual graph gives a compact overview; the subset column preserves the reasoning behind each generated state. The converter accepts ordinary labelled transitions and epsilon transitions, so it also supports ε-NFA examples.
You can begin with the built-in sample or continue from another tool. An automaton handed over from the regular-expression converter or simulator is loaded and converted automatically. After conversion, the result can be passed directly to the DFA minimizer or the finite-automata simulator through the buttons below the output.
Enter states and transitions
Choose Add State and click the canvas to place a state. Use Select / Drag to select or move it, then use the selected-state controls to set its start or accepting status. Give states distinct, meaningful names so the subset column remains easy to read. A conversion needs a marked start state; without one, the tool asks you to select one.
Choose Add Transition and select its source and destination states. Enter a single symbol or comma-separated alternatives such as a,b. The editor recognizes ε, and its prompt also accepts e as shorthand for an epsilon-only edge. Use the actual epsilon character when you want the meaning to be unambiguous, especially on combined labels.
Epsilon means that a transition consumes no input. It is not an ordinary alphabet symbol and does not receive its own column in the converted table. If the assignment has an explicit alphabet, check that its symbols occur in your entered transitions; the converter derives its alphabet from those labels rather than from a separate alphabet field.
How subset construction works
Each generated DFA state represents a set of NFA states. The initial set is ε-closure({start}), meaning the start state plus every state reachable from it using only epsilon edges. A closure always includes the states you started from, even when no epsilon edge exists.
For each input symbol, first collect every destination reachable from any member of the current subset on that symbol. Then take the epsilon closure of the collected destinations. In compact notation, δD(S, a) = ε-closure(move(S, a)). Repeat this process for each newly discovered subset until there are no unprocessed reachable subsets.
A generated state is accepting when its subset contains any accepting NFA state. It does not need all its members to be accepting. This preserves the NFA rule that a string is accepted if at least one complete path finishes in an accepting state after all input has been consumed.
Worked example: strings ending in ab
The default NFA has start state q0, intermediate state q1 and accepting state q2. State q0 loops on a and b, q0 also moves to q1 on a, and q1 moves to q2 on b. There are no epsilon edges in this example. The following rows were generated using the component's subset-construction steps.
| DFA state | NFA subset | On a | On b | Accepting? |
|---|---|---|---|---|
| A0 | {q0} | A1 | A0 | No |
| A1 | {q0,q1} | A1 | A2 | No |
| A2 | {q0,q2} | A1 | A0 | Yes |
On a, the NFA can stay at q0 and also enter q1, so A1 contains both states. Reading b next leaves a path at q2, giving accepting state A2. Another b returns to A0 because the string no longer ends in ab. Use the simulator handoff to follow these transitions one symbol at a time.
The example has three NFA states, so the full powerset contains eight possible subsets. Only three nonempty subsets are reachable here, and the converter builds those reachable subsets rather than listing every theoretical combination. A different NFA can produce many more subsets, so start with a small graph when learning the method.
Empty transitions and the trap state
A table cell containing ∅ means no NFA state remains active after that move and its closure. The converter leaves the corresponding edge and empty-subset state out of the drawing to keep the graph compact. This is a partial DFA representation: a missing transition rejects the input.
If your course requires a total DFA, add an explicit nonaccepting trap state on paper or in an editor. Every missing transition must go to that state, and the trap state must loop on every alphabet symbol. The graph produced here does not automatically draw those trap-state loops, so account for that convention when comparing with a textbook solution.
Check equivalence and continue
Compare the NFA and DFA on accepted and rejected strings, including the empty string when epsilon paths might reach an accepting state. One matching example is not a proof of equivalence, but tracing boundary cases is a useful way to catch an incorrectly entered edge or accepting marker before submitting your work.
Use the NFA/DFA simulator to inspect execution, or the DFA minimizer to merge equivalent states after determinization. Subset construction does not itself guarantee a minimum-state DFA. For a detailed written walkthrough, read the subset construction guide; if your starting point is a pattern, begin with the regex to NFA converter.