Developer tool
NFA to DFA Converter
Convert a nondeterministic finite automaton to a DFA with the subset (powerset) construction. Build your NFA in an editable table and test strings on the result.
| State | Start | Accept | a | b | ε |
|---|---|---|---|---|---|
| q0 | |||||
| q1 |
Type target state numbers in each cell, separated by commas. A state can go to several targets (nondeterministic), so “0, 2” is valid, and the ε column adds epsilon moves. Leave a cell empty for no transition.
Your NFAInput
The nondeterministic automaton defined in the table above.
start stateaccepting state
DFASubset construction
Each DFA state is the set of NFA states reachable together after an epsilon-closure.
| State | a | b |
|---|---|---|
| S0{q0} | S1 | S0 |
| S1{q0,q1} | S1 | S0 |
start stateaccepting state
Type a string to trace it through the automaton. The empty string is allowed.
About this tool
Convert an NFA to a DFA with subset construction
The subset construction (powerset construction) is the second stage of a lexical analyzer generator. It removes nondeterminism by tracking the set of NFA states the machine could occupy simultaneously: every state of the new DFA is one such subset. Starting from the epsilon-closure of the NFA's start state, the algorithm reads each alphabet symbol, follows every possible move, takes the epsilon-closure again, and records the resulting subset as a DFA state. A DFA state is accepting whenever its subset contains any accepting NFA state.
Enter your NFA directly in the transition table, including nondeterministic moves and epsilon transitions, and the tool builds the equivalent DFA live. It shows your NFA as a diagram, the resulting DFA as a diagram and transition table with each state's source subset labeled, and a string tester so you can confirm both machines accept the same language.
How it works
Convert an NFA in three steps
- 1Define the NFA
Set the alphabet and states, pick the start and accepting states, and click cell targets to add moves.
- 2Read the DFA
See the subset-construction DFA as a diagram and table, with each state labeled by its NFA subset.
- 3Test a string
Type an input to trace it through the DFA and confirm it is accepted or rejected.
Common questions
Subset construction FAQ
What is the subset construction?
The subset construction, also called the powerset construction, converts an NFA into an equivalent DFA. Each DFA state represents a set of NFA states that the machine could be in at once. The start state is the epsilon-closure of the NFA start, and for each input symbol the DFA moves to the epsilon-closure of every NFA state reachable on that symbol.
How do I enter my NFA?
Use the editable transition table. Set the alphabet, add states, choose the start state and accepting states, then click the target numbers in each cell to add moves. A cell can have several targets (that is the nondeterminism), and the ε column adds epsilon moves.
Why does the DFA have fewer or more states than my NFA?
The DFA has one state per reachable subset of NFA states, so a small NFA can expand into more DFA states, while an NFA with lots of overlap can collapse into fewer. This tool only builds the subsets that are actually reachable from the start state.
What is an epsilon-closure?
The epsilon-closure of a set of states is every state reachable from it using only epsilon (ε) moves. Subset construction takes the epsilon-closure at every step so that free moves are accounted for before reading the next symbol.
Is my automaton uploaded anywhere?
No. The conversion runs entirely in your browser. Nothing you enter is sent to a server.