The Subset Construction Algorithm: NFA/ε-NFA to DFA

The Theory of Computation is a branch of computer science that focuses on understanding the nature and limits of computation. It explores the fundamental principles underlying the design and analysis of algorithms, as well as the classification of computational problems.

One important concept in automata theory is the subset construction algorithm, which plays a significant role in converting a nondeterministic finite automaton (NFA) or nondeterministic finite automaton with epsilon (i.e. ε) transition(s) into its equivalent deterministic finite automaton (DFA). Its purpose is to create a DFA that simulates the behaviour of the NFA, allowing for deterministic and predictable computations. This algorithm is crucial for converting NFAs (or ε-NFAs) that are easier to construct into DFAs that can be executed more efficiently. The purpose of this blog post is to comprehend the concept of the subset construction algorithm with several working examples.

Figure 1: A sample ε-NFA

We first need to elaborate on the concept ε-closure(T). It is worth noting that T can be a single state, multiple states, or a transition function. In an NFA or ε-NFA, ε-closure (T) is the set of all states that can be reached from T by following only ε-transitions. In other words, it is the set of states that can be reached without consuming any input or incurring any cost.

For example, in Figure 1, ε-closure (A) = {A, B, C} indicates that without incurring any cost, we can arrive at states A, B and C. Note that, subset construction algorithm uses this ε-closure (initial state of the given NFA/ε-NFA) to find the initial state of the desired DFA.

In any case, for multiple states, ε-closure (A, E) = {A, B, C, E} and ε-closure (C, D) = {C, D}. This is simply the union of the results from each state.

Now, what will happen if the T of ε-closure (T) is a transition function?

For instance, ε-closure (δ (A, a)) = φ; ε-closure (δ (B, a)) = {D} and ε-closure (δ (C, a)) = φ. Hence, in the δ({A, B, C}, a) = φ ∪ {D} ∪ φ = {D}. In the subset construction algorithm, this {D} forms a new state.

Table 1: The transition table representing DFA converted from the ε-NFA of Figure 1.

Figure 2: A sample NFA

Table 2: The DFA corresponds to the NFA of Figure 2. Here, all the states involving D (the final state of the original NFA) are considered final states in the DFA.

Figure 3: Another sample ε-NFA

Table 3: The transition table of a DFA produced from ε-NFA of Figure 3

Figure 4: Another ε-NFA with four states and three ε-transitions

Table 4: The DFA corresponds to the ε-NFA of Figure 4. Here {A, D, C} forms the initial state as ε-closure (A) = {A, D, C}. Then, ε-closure (δ (A, 0)) = ε-closure (B) = {B, A, D, C}; ε-closure (δ (D, 0)) = ε-closure (A) = {A, D, C} and ε-closure (δ (C, 0)) = ε-closure (B) = {B, A, D, C}. As a results, the union of all the produces a new state {A, B, D, C} for δ ({A, D, C}, 0).

Figure 5: A bit more complex ε-NFA sample.

Table 5: The solution of the sample of Figure 5.

When converting an NFA to a DFA, there is no guarantee that we will have a smaller DFA. Rather, the resulting DFA can have a significantly larger number of states, which can make the construction process impracticable in some cases. To be specific, if the NFA consists of n states, the resulting DFA may contain up to 2^n states, a number that is exponentially larger. Having said that, there exist algorithms that can minimise a DFA by removing redundant states and transitions.