How to convert NFA to DFA

NFA vs. DFA

A deterministic finite automaton has one transition from one state to another. On the other hand, a nondeterministic finite automaton has one or more than one transition from one state to another or itself.

Every deterministic finite automaton is a nondeterministic finite automaton but the reverse is not true.

Subset construction method

Assume an NFA for a language L with $<Q, Σ, q_0, δ, F>$ where

• $Q$ is the finite set of states

• $Σ$ is the input symbols

• $q_0$ is the start state

• $δ$ is the transition function

• $F$ is the final state

It is converted to a DFA $<Q', Σ, q_0, δ', F'>$ where

• $Q'$ is the new finite set of states

• $Σ$ is the input symbols

• $q_0$ is the start state

• $δ'$ is the transition function

• $F'$ is the new final state

Note: While converting an NFA with n states to a DFA, 2ⁿ possible set of states can be reachable but not necessarily reached in the DFA.

The following general set of rules are followed to convert a nondeterministic finite automaton to a deterministic finite automaton:

1. At the beginning $Q'$ = $∅$.

2. Add $q_0$ to $Q'$.

3. For every state in $Q'$, find the possible set of states for each input symbol using the transition function of the NFA. If the acquired set of states is not present in $Q'$, add it.

4. The final state $F'$ will be all those states that have $F$ in them.

Example

Let's consider the following nondeterministic finite automaton that accepts the language $\{{aa, aab}\}^*\{{b}\}$.

For this NFA, $q0$ is the start state.

Step 1: Q' is empty

Checks if $Q'$ is empty.

Step 2: Add the first state to Q'

Add the first state to $Q'$ such that it now has $q_0$.

Step 3: Find states for each input symbol

For each state in $Q'$, we will find the states for each of the input symbols. $Q'$ has $q_0$ presently. Check transitions for '$a$' and '$b$' from the transition table for $q_0$. Update the table as new states are reached.

Step 3.1:

Step 3.2:

Step 3.3:

Step 3.4:

Step 4: Result

Combine all the states in the last obtained transition table and show appropriate transitions. In case a transition is not defined for input, make a transition to the trap state.

For this DFA, $q0$ is the start state.