4 Conversion of NFA to DFA


4.1 The Subset Construction


To convert the NFA to DFA we will use Rabin and Scott's Subset Construction. Central to this is the concept of the closure. One of the major steps of the subset construction is:

Find the ε-closure for each state.

This is defined as:

The ε-closure of state 0 is the set of all states reachable from 0 by zero or more ε-transitions.

A full explanation of the steps involved in the subset construction is as follows.

First, we take the starting state q0. We want to find the ε-closure for this state. Once we have this set we define it as the start state q0 for our new DFA. We also add this set of states to a list of stored sets of states that we will call DFAstates. Next we look at each of the states in the NFA reached by this first ε-closure. For each of these states in turn we will see which further states are reachable by a closure under each of the symbols in the alphabet followed in each case by the ε-closure for each of these states. This set of states will be compared to DFAstates. If this new set is not found in the list, a new state is created in the new DFA. If it is, this state points to a state in the DFA that already exists.

In pseudocode3:

While there is an uninvestigated state S in the set of DFA states D
	get the next state S from the NFA
	for each a ∈ Σ
		R = ε-closure(move(S, a))
		if R ∉ DFA
			add R as an uninvestigated state to D
			State S transitions to new state R by symbol a
		else
			State S transitions to previous state R by symbol a

The above explanations are quite dense and are best explained by some examples. It is worth noting that the DFA created by this process tend to have a lot of redundant states. We will deal with this in our section on state minimisation. For now, for our first example we will use the NFA created from the regular expression (a | b)* c shown above in illustration 11.