ToolSphere

NFA to DFA Converter

Computer science

Convert an NFA or ε-NFA to a DFA online. Draw transitions, inspect the subset construction table and graph, then send the result to trace or minimize.

NFA to DFA converter

Describe the language or draw your NFA below, then press Convert to DFA. Each DFA state is a set of NFA states (the subset construction).

DFA states: {q0}; {q0,q1}; {q0,q2}. The transition table and diagram appear below; the empty-subset trap is omitted.

Your NFA (type ε for an empty move that reads no symbol)

Drag a state to move it. Click a state to make it start or accepting, rename or delete it.

a,babq0q1q2

Subset construction table

DFA stateNFA states it stands forOn 'a'On 'b'
A0{q0}A1A0
A1{q0,q1}A1A2
A2{q0,q2}A1A0

The DFA

abababA0A1A2

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

Coming from JFLAP? See what carries over and what JFLAP still does better →

Try next

How to use NFA to DFA Converter

  1. 1No NFA drawn? Type the question, such as "third symbol from the end is 1 over {0,1}", and press Build NFA: the textbook NFA is drawn and converted at once.
  2. 2Use the sample NFA or edit the graph with Add State, Add Transition and Select / Drag.
  3. 3Mark one state as the start and mark the accepting states in the selected-state controls.
  4. 4Label edges with symbols, comma-separated alternatives such as a,b, or ε for an epsilon transition.
  5. 5Click Convert to DFA and match each A-numbered state with its NFA subset in the table.
  6. 6Inspect the resulting graph, then use Trace it in the simulator or Minimize this DFA to continue with the same automaton.

About NFA to DFA Converter

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.

Guides and tutorials

Frequently asked questions

Can I convert an NFA without drawing it?

Yes. Type the language in Type the question and press Build NFA. For ends with, contains and k-th symbol from the end it draws the textbook NFA and runs the subset construction straight away; other descriptions load their minimal DFA.

How do I convert an NFA to a DFA online?

Draw or edit the NFA, mark its start and accepting states, then click Convert to DFA. Read the subset column to see which original states each generated DFA state represents.

Does this converter support epsilon transitions?

Yes, enter ε for a transition that consumes no input. Epsilon closures are applied to the initial state and after each symbol move.

Is NDFA to DFA the same conversion?

Yes, NDFA is another name used for a nondeterministic finite automaton. The same subset-construction method applies.

Why does a DFA state contain several NFA states?

An NFA can have multiple active possibilities after the same input. A single DFA state records that whole set so its next transition is deterministic.

How are accepting DFA states chosen?

A generated state is accepting if any member of its NFA subset is accepting. This follows the NFA acceptance rule that one successful complete path is enough.

What does ∅ mean in the conversion table?

It means that no destination state is active for that symbol move. The graph omits the empty-subset trap state, so a missing transition rejects the string.

Does the converter produce a complete DFA?

It can display a partial DFA by omitting empty-subset transitions and the trap-state drawing. If a complete transition function is required, add a rejecting trap state and the missing edges for the alphabet.

Does subset construction also minimize the DFA?

No, reachable subsets can still be equivalent to one another. Use Minimize this DFA below the output to continue with the generated automaton.

Can multiple symbols share an NFA edge?

Yes, enter comma-separated alternatives such as a,b. The converter expands them into individual symbol transitions before building the subsets.

How can I check the converted DFA?

Use Trace it in the simulator to pass the generated DFA to the simulator. Compare accepted and rejected strings with the original NFA, and check epsilon-related empty-string behavior when relevant.

Have a suggestion for NFA to DFA Converter?Share your feedback ↗