Converting A NFA To A DFA
Written by Luka Kerr on May 6, 2019
To convert a NFA to a DFA, we can use a technique known as subset construction.
The NFA
An NFA is composed of 5 things:
- A set of states $Q$
- A language $\Sigma$
- A transition function $\delta$ that maps a state and an input letter to a set of states
- A starting state $q_0$
- A set of final states $F$
Formally, we can write this as a 5-tuple $N = (Q, \Sigma, \delta, q_0, F)$.
For this walkthrough, we will be using the following NFA:
This NFA has:
- A set of states $Q = \{q_0, q_1, q_2, \dots, q_9 \}$
- A language $\Sigma = \{\text{a}, \text{b} \}$
- A transition function $\delta$
- A starting state $q_0$
- A set of final states $F = \{q_9 \}$
Prerequisites
Before we get started, we need to define the function $\epsilon$-closure($s$).
For some state $s$:
- $s \sube \epsilon$-closure($s$)
- For every $s^\prime \in \epsilon$-closure($s$), $\delta(s^\prime, \epsilon) \sube \epsilon$-closure($s$)
Essentially what this is saying is that the $\epsilon$-closure of a state $s$ is itself, and any state that can be reached from $s$ using one or more epsilon transitions.
For example, in the NFA above, $\epsilon$-closure($q_5$) is $\{ q_5, q_6, q_8, q_9 \}$.
We will also extend this definition to handle sets of states. That is, $\epsilon$-closure($S$) is the union of each set $\epsilon$-closure($s$) for every $s \in S$.
Step 1: NFA Transition Table
First we setup a NFA transition table, which contains rows for every state in the NFA, and columns for each letter in the language $\Sigma$, including $\epsilon$-closure’s for each transition for each input letter.
| States | a | b | $\epsilon$ | $\epsilon$-closure($\delta$($q_n$, a)) | $\epsilon$-closure($\delta$($q_n$, b)) |
|---|---|---|---|---|---|
| $q_0$ | $q_1$ | $\{q_2, q_4 \}$ | |||
| $q_1$ | $\{q_2, q_4 \}$ | ||||
| $q_2$ | $q_3$ | $q_9$ | |||
| $q_3$ | $q_9$ | ||||
| $q_4$ | $q_5$ | $\{q_6, q_8, q_9 \}$ | |||
| $q_5$ | $\{q_6, q_8, q_9 \}$ | ||||
| $q_6$ | $q_7$ | $\{q_6, q_8, q_9 \}$ | |||
| $q_7$ | $\{q_6, q_8, q_9 \}$ | ||||
| $q_8$ | $q_9$ | ||||
| $q_9$ |
Step 2: DFA Transition Table
After creating the NFA transition table, we can either go straight to a DFA, or write a DFA transition table first. We will take the intermediary step of creating a DFA transition table and then create the final DFA after.
Before creating the DFA transition table, we should recall our starting and final state(s).
- Starting: $q_0$
- Final: $q_9$
Now we can create the DFA transition table. This involves the following steps:
- Begin at the starting state $q_0$
- For each letter in $\Sigma$, add states reachable from $q_0$, including $\epsilon$ and $\epsilon$-closure($\delta$($q_n$, $\alpha$))
- From the states found in step 2, if there are any new states not in the DFA transition table, add them to the DFA transition table and
goto1 for each of the new states
Once there are no new states to be added, we can mark any states that are final. This is done by looking for states that contain any final states, in our case just states that contain $q_9$.
Lets go through converting the NFA transition table above to a DFA transition table.
Beginning at $q_0$, we get:
| States | a | b |
|---|---|---|
| $q_0$ | $\{q_1, q_2, q_4 \}$ |
As you can see, the states reachable from $q_0$ are $q_1$, and $\{q_2, q_4 \}$ from $\epsilon$-closure($q_0$, a). There are no states reachable from $q_0$ for the letter b.
Now, as you see we have a new state, namely $\{q_1, q_2, q_4 \}$. We need to add this to the DFA transition table and repeat the same process.
Beginning at $\{q_1, q_2, q_4 \}$, we now get:
| States | a | b |
|---|---|---|
| $q_0$ | $\{q_1, q_2, q_4 \}$ | |
| $\{q_1, q_2, q_4 \}$ | $\{q_3, q_9 \}$ | $\{q_5, q_6, q_8, q_9 \}$ |
When we have a set of states, such as $\{q_1, q_2, q_4 \}$, we look at states reachable from any state in that set. In this case, for the letter a, states $q_3$ and $q_9$ are reachable from states $q_1, q_2, q_4$. Again, this includes states in $\epsilon$-closure($q_n$, a) for $n \in \{1, 2, 4 \}$.
Now again, we have two new states, namely $\{q_3, q_9 \}$ and $\{q_5, q_6, q_8, q_9 \}$. We will add these to the DFA transition table, and repeat the same process for both new states.
| States | a | b |
|---|---|---|
| $q_0$ | $\{q_1, q_2, q_4 \}$ | |
| $\{q_1, q_2, q_4 \}$ | $\{q_3, q_9 \}$ | $\{q_5, q_6, q_8, q_9 \}$ |
| $\{q_3, q_9 \}$ | ||
| $\{q_5, q_6, q_8, q_9 \}$ | $\{q_6, q_7, q_8, q_9 \}$ |
From these two new states, only one has added a new state $\{q_6, q_7, q_8, q_9 \}$. We can see that this again is a new state, and we will add it to the DFA transition table, and repeat the process again.
| States | a | b |
|---|---|---|
| $q_0$ | $\{q_1, q_2, q_4 \}$ | |
| $\{q_1, q_2, q_4 \}$ | $\{q_3, q_9 \}$ | $\{q_5, q_6, q_8, q_9 \}$ |
| $\{q_3, q_9 \}$ | ||
| $\{q_5, q_6, q_8, q_9 \}$ | $\{q_6, q_7, q_8, q_9 \}$ | |
| $\{q_6, q_7, q_8, q_9 \}$ | $\{q_6, q_7, q_8, q_9 \}$ |
The new state again has only added one state, but it already exists in the DFA transition table, and no other new states were added. This means that the DFA transition table is done.
We can now mark any states that are final. Remember, this is done by looking for states containing any final states from the original NFA. In our example, the only final state is $q_9$, and so the final states of our DFA transition table are
- $\{q_3, q_9 \}$
- $\{q_5, q_6, q_8, q_9 \}$
- $\{q_6, q_7, q_8, q_9 \}$
Step 3: Creating The DFA
After creating the DFA transition table, all we need to do is translate it into a DFA.
This is done simply by creating each state as a node, and writing in the transitions from each state for each applicable letter in $\Sigma$ ($\{\text{a}, \text{b} \}$). Don’t forget to indicate the starting state ($q_0$) and final states mentioned above!
Below is the resulting DFA:
