NFA to DFA Converter

Use the free NFA to DFA converter below to turn any NFA into an equivalent DFA, or learn how to convert NFA to DFA yourself with worked NFA to DFA conversion examples and practice problems.

How to Convert NFA to DFA: Subset Construction Algorithm

Follow these steps to master NFA to DFA conversion.

NFA to DFA Conversion Examples

Walk through a complete NFA to DFA conversion example using the subset construction algorithm.

Problem: Convert the following NFA to DFA.

NFA Definition: States {q0, q1, q2}, alphabet {0,1}, start state q0, final state q2. Transitions: δ(q0,0) = {q0,q1}, δ(q1,1) = {q2}.

Step 1: Start state DFA = ε-closure(q0) = {q0} (call it state A)

Step 2: From {q0}, on 0: move({q0},0) = {q0,q1} → ε-closure = {q0,q1} (new state B)

Step 3: From {q0}, on 1: move({q0},1) = {} → ε-closure = {} (dead state)

Step 4: From {q0,q1}, on 0: move = {q0,q1} → ε-closure = {q0,q1} (state B again, so no new state)

Step 5: From {q0,q1}, on 1: move = {q2} → ε-closure = {q2} (new state C, final because it contains q2)

Result: DFA with states A = {q0}, B = {q0,q1}, C = {q2} (final), plus the dead state ∅. The full transition table for Example 1 is in the “Subset Construction Algorithm: Transition Table” section further down this page. Examples 2 and 3 below show their tables right under the steps.

Example 2: NFA for strings ending in 01

NFA: States {q0, q1, q2}, alphabet {0,1}, start q0, final q2. Transitions: δ(q0,0) = {q0,q1}, δ(q0,1) = {q0}, δ(q1,1) = {q2}. There are no ε-moves, so every ε-closure is the set itself.

Step 1: Start: ε-closure(q0) = {q0}, so the DFA start state is A.

Step 2: From A = {q0}, on 0: move = {q0,q1} → ε-closure = {q0,q1} = B (new state)

Step 3: From A = {q0}, on 1: move = {q0} → ε-closure = {q0} = A

Step 4: From B = {q0,q1}, on 0: move = {q0,q1} → ε-closure = {q0,q1} = B

Step 5: From B = {q0,q1}, on 1: move = {q0,q2} → ε-closure = {q0,q2} = C (new state)

Step 6: From C = {q0,q2}, on 0: move = {q0,q1} → ε-closure = {q0,q1} = B

Step 7: From C = {q0,q2}, on 1: move = {q0} → ε-closure = {q0} = A

Result: only 3 DFA states are reachable (not 2³ = 8). C is final because it contains q2.

→ start state, * final state

Example 3: NFA with an ε-transition

NFA: States {q0, q1, q2}, alphabet {a,b}, start q0, final q2. Transitions: δ(q0,ε) = {q1}, δ(q0,a) = {q0}, δ(q1,b) = {q1,q2}, δ(q2,a) = {q2}.

Key point: the DFA start state is ε-closure(q0) = {q0,q1}, not just {q0}, because q0 can move to q1 without reading anything. After every move, take the ε-closure again.

Step 1: Start: ε-closure(q0) = {q0,q1}, so the DFA start state is A.

Step 2: From A = {q0,q1}, on a: move = {q0} → ε-closure = {q0,q1} = A

Step 3: From A = {q0,q1}, on b: move = {q1,q2} → ε-closure = {q1,q2} = B (new state)

Step 4: From B = {q1,q2}, on a: move = {q2} → ε-closure = {q2} = C (new state)

Step 5: From B = {q1,q2}, on b: move = {q1,q2} → ε-closure = {q1,q2} = B

Step 6: From C = {q2}, on a: move = {q2} → ε-closure = {q2} = C

Step 7: From C = {q2}, on b: move = ∅ → ε-closure = ∅ = ∅ (new state)

Step 8: ∅ is the dead state: it goes to itself on every symbol.

Result: B and C are final because they contain q2.

→ start state, * final state

Subset Construction Algorithm: Transition Table

The subset construction algorithm creates a transition table for the DFA.

Common Mistakes in NFA to DFA Conversion

Avoid these errors when using an NFA to DFA converter.

Frequently Asked Questions

Common questions about NFA to DFA conversion and the subset construction algorithm.

What is an NFA to DFA converter?

An NFA to DFA converter is a tool or algorithm that transforms a nondeterministic finite automaton into an equivalent deterministic finite automaton. The subset construction algorithm is the standard method used for this conversion.

How to convert NFA to DFA step by step?

How to convert NFA to DFA involves 4 steps: (1) Find ε-closure of start state, (2) For each input symbol, compute transitions, (3) Create new DFA states from reachable sets, (4) Mark final states. This is the subset construction algorithm.

Why is the subset construction algorithm important?

The subset construction algorithm is the foundation of NFA to DFA conversion. It proves that NFAs are not more powerful than DFAs — any language accepted by an NFA can also be accepted by a DFA.

Where can I find more NFA to DFA conversion examples?

This page provides NFA to DFA conversion examples. For additional practice, check external resources like GeeksforGeeks and TutorialsPoint.

Can NFA to DFA conversion increase the number of states?

Yes, NFA to DFA conversion can cause state explosion. A DFA may have up to 2ⁿ states where n is the number of NFA states. The subset construction algorithm generates all possible subsets of NFA states.

Additional Resources

Explore more about automata theory and finite automata.

Still Stuck with NFA to DFA Conversion?

Tried the subset construction algorithm but still confused? Don’t spend hours stuck on the same conversion.

📋 Before you submit:

• Be specific about the NFA you’re trying to convert (states, alphabet, transitions, start state, final states)
• Share where exactly you’re getting stuck — ε-closure? subset construction? transition table?
• Include any steps you’ve already completed (e.g., “I found the ε-closure of q0 = {q0,q1}”)
• If applicable, provide a diagram description or state transition table

Fill out the form below

🔒 Your email is safe with us. We’ll never share your information. Questions may be anonymized and added to our FAQ to help other students.

⚠️ Important Disclaimer

This form is for educational assistance only. We aim to respond within 24-48 hours, but response times may vary based on volume.

While we strive to provide accurate, step-by-step explanations, we cannot guarantee the correctness of every solution. Our guidance is meant to help you learn — not to replace your own work or your professor’s instruction.

For urgent exam questions, please consult your professor or teaching assistant. We do not provide last-minute solutions.

Get More Automata Theory Resources

Subscribe to get new NFA to DFA conversion examples, subset construction practice problems, and theory of computation study guides delivered to your inbox.

No spam. Unsubscribe anytime.

More NFA to DFA Practice Problems