The Subset Construction Three Ways
Cameron Moy July 23, 2018
Here we present three methods of performing the subset construction, from the most explicit (and mechanical) to the least. We will use the following NFA as our example for each of the methods.
a
b
start 0 aa
Before we start, let’s define two important operations over NFAs.
Definition. The ε-closure of a set of states R ⊆ Q is the set of states reachable
from any state in R taking zero or more ε-transitions.
Definition. ThemoveofasetofstatesR⊆Qonsymbolt∈Σisthesetof
states reachable from exactly one t transition from any state in R. 2-Table
This method involves the most writing, but the extra bookkeeping can help prevent mistakes. We transfer information from the diagram into table one. In table two we construct the subsets that determine our DFA.
1. We’ll have a column for each symbol in Σ (the moves) and for ε∗ (the ε-closure).
1
1 ε 3 ε
b 2a4
Preliminaries
2. For every state q ∈ Q we will calculate the move of {q} on each symbol. After that calculate the ε-closure of {q} in the final column. This finishes table one.
3. Now for table two. Here, every row corresponds to a subset, starting with the ε-closure of the start state singleton {q0}. Each column will calculate the move of this subset on a different symbol in Σ followed by an ε-closure. New subsets generated will start a new rows. If the subset contains an accepting state, it gets underlined (this becomes accepting in the DFA).
4. This table completely determines the DFA.
Example. We begin with the first table. This will extract all the information we need from the diagram. After we have generated this table we don’t have to look at the picture at all.
a b ε∗ 0 {1,2} ∅ {0} 1 ∅ {0} {1}
2 {0} ∅ {1,2,3} 3 ∅ {4} {1,3} 4 {2} ∅ {4}
Now we can start constructing subsets.
aε∗ {0} {1, 2, 3}
bε∗ ∅ {0, 4}
{1, 2, 3} {0}
{0,4} {1,2,3} ∅
∅∅∅
This uniquely determines the equivalent DFA.
2
start {0} b
b a,b ∅ b {0,4}
a
{1, 2, 3}
a
a
1-Table
Notice that the first table isn’t really necessary. It encodes all the same infor- mation as the state diagram itself. Instead of writing out this table explicitly we can compute everything we need for the second table on-the-fly directly from the diagram.
This is a slightly more error prone method, but for some NFAs it can save a significant amount of some writing. I would recommend using this method above the others.1
0-Table
Here we don’t use the tables at all. We do everything in our head step-by-step by keeping track of which states we have and haven’t processed. Only use this method if you’re very comfortable with the construction and are careful.
Example. We start with the ε-closure of q0 and compute all the subsets tran- sitioning from that.
1Thanks to my colleague Justin Stackman for suggesting this variation.
3
start {0} b
{1, 2, 3}
a
∅
Notice that one of the states we generated, namely {1,2,3} contains the accepting state 1. Therefore, we also must make it accepting. Next we will compute the transitions out of another subset. Following along with the same sequence as the table methods, we will process {1, 2, 3}.
start {0} b
a
a
{1, 2, 3}
b ∅ {0,4}
Next up is the state {0,4}. This one was newly generated by processing {1, 2, 3}.
a
start {0} b
b ∅ b {0,4}
{1, 2, 3}
a
a
4
Finally, we finish off with the dead state ∅. This doesn’t generate any new subsets and we’ve processed all the other states. Hence, we’re done.
a
start {0} b
b a,b ∅ b {0,4}
{1, 2, 3}
a
a
5