Powerset construction

From Wikipedia, the free encyclopedia

In the theory of computation, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same formal language. It is important in theory because it establishes that NFAs, despite their additional flexibility, are unable to recognize any language that cannot be recognized by some DFA. It is also important in practice for converting easier-to-construct NFAs into more efficiently executable DFAs. However, if the NFA has n states, the resulting DFA can have up to 2ⁿ states, exponentially more, which sometimes makes the construction impractical for large NFAs.

Contents 1 Motivation 2 Example 3 Example 2 4 Defining the DFA 5 Formal definition 6 References

[edit] Motivation

Recall that an NFA is like a DFA except that at certain nodes, it can "branch", following a number of paths forward simultaneously. The NFA will accept if one of its paths ends up at an accepting state when the computation completes. If all of its paths fail, it will reject. For example, in the diagram in the example section, if we are at state 2 and the next input symbol is a 1, the machine branches, proceeding to both states 2 and 4.

Notice that no matter how many different paths the NFA might be following, each of them must be in one of the n states. For this reason, we can succinctly sum up the current configuration of the NFA as the set of states it could be in at that moment, given some previous sequence of choices. Moreover, if we know the set of states the NFA is currently in, we can figure out what set of states it will visit next based on the next input token. This is the key to the algorithm.

[edit] Example

Consider the following NFA with alphabet {0, 1}:

We will construct an equivalent DFA; the final result is shown below. We begin with the start state. The NFA starts in state 1, but it can also, without seeing any input, proceed to states 3 and 2 along ε edges. Therefore we must consider it to be in all these states simultaneously initially. We do this by creating a start state for our DFA and labelling it "{1,2,3}".

Next, suppose we see the input character 0. If we stayed in state 1, we can follow the edge labelled "0" to state 2. If we went to state 3, we can proceed to state 4. If we went to state 2, however, we'd be stuck; there's no "0" edge out of state 2. This means the NFA forgets about the old state 2 path; it is now in states 2 and 4. In the DFA, we express this with a new state labelled "{2,4}" and an edge labelled "0" from the start state to the new state.

Suppose we saw a 1 instead initially. Then both the path in state 1 and the path in state 3 cannot proceed, but the path in state 2 can, and it branches: it both remains in state 2 and proceeds to state 4. Thus, the NFA is now in states 2 and 4 — exactly the same as for the 0 input, but for a different reason. We represent this by adding the label "1" to our edge from the start state to the existing "{2,4}".

Now, suppose we're in the "{2,4}" state and we see a 1. The path in state 4 cannot proceed, but the path in state 2 goes to both 2 or 4, again. We remain in state "{2,4}". If we see a 0, however, we can't proceed from state 2, but we can proceed from state 4 to state 3. Moreover, after we reach state 3, we branch and follow the ε-edge to state 2 as well. The result is that we are in states 2 and 3. We represent this with a new node in the DFA labelled "{2,3}" and an edge labelled "0" from {2,4} to {2,3}.

The final result DFA

If we see a 1 in the state {2,3}, the path in state 3 cannot proceed, but the path in state 2 goes to states 2 and 4, as before, so we return to the node {2,4}. If we see a 0 however, the path in state 2 cannot proceed, while the path in state 3 can reach state 4. Thus, we could only be in state 4. We create a new node labelled "{4}" and an edge labelled "0" from {2,3} to {4}.

Finally, if we're in state {4} and we see a 0 as input, we proceed to states 2 and 3, as before, so there is an edge labelled "0" from {4} to {2,3}. If we see a 1, however, all of our remaining paths are stuck and the machine must reject. How do we ensure this? We create a new node, which we will label "", from which there is no escape; all its outgoing edges point to itself, and it is not an accepting state. We then add an edge from {4} to labelled 1.

We've now considered all possible cases. All we have to decide is which states in our DFA should accept. Since the NFA accepts if any of its paths end up in an accepting state, we can mimic this by setting all the DFA nodes that include an accepting NFA state, namely {1,2,3}, {2,3}, {2,4}, and {4}, as accepting. The resulting DFA accepts exactly the same set of strings as the original NFA. Note that the DFA is larger than the original NFA.

[edit] Example 2

Consider the following NFA:

• S_n={A,B,C}
• ∑_n={0,1}
• s_n=A
• A_n={C}

Equivalent DFA has 2^|S_n|=2³=8 states:

• S_d'={α,β,γ,αβ,αγ,βγ,αβγ,ω}

α corresponds to A, β corresponds to B, γ corresponds to C

αβ can be reached, for example, when from A exist 2 edges labelled "0": A→A and A→B. A × 0 → {A,B}

• ∑_d'={0,1}
• s_d'=α
• A_d'={γ,αγ,βγ,αβγ}

After removing states that cannot be reached from s_d' we get final DFA:

• S_d={α,αβ,βγ,ω}
• ∑_d={0,1}
• s_d=α
• A_d={βγ}

[edit] Defining the DFA

Let's generalize the procedure of the previous section. There are four important questions we must answer to define a DFA:

• What are the states?
• Which of these states are accepting states?
• What state is the start state?
• Where do we place edges and with what labels?

We need a state of the DFA to describe each possible configuration of the NFA. But, in general, the NFA might be at any subset of its states at any given point. The set of subsets of a set S is called its power set, written P(S), and so we define the set of states in the DFA to be the power set of the set of states in the NFA. This answers the first question.

We already mentioned that if any of the NFA's parallel paths is in an accepting state at the end, then the NFA accepts. The DFA can mimic this by accepting in any state that contains one of the NFA's accepting states. This answers the second question.

Now, for the third question. Suppose that the input string given to the NFA is the empty string. What states can it visit before it must stop? It can't follow any edges that are labelled with an input symbol, but it can follow ε edges, which consume no input. Thus, it can visit any state that is reachable from the start state using just ε edges. This set of states is formally called the ε-closure of the start state. Because our DFA can't do anything when given an empty input string except halt immediately, we must be sure its start state includes the possibility of all these states. We do this by setting its start state to the ε-closure of the NFA's start state.

Finally, we will answer the fourth question using similar ideas. Suppose we're in a particular state of the DFA (that is, a particular set of states in the NFA) and we see a particular input symbol. We want to know what DFA state to go to next. This will be precisely the set of NFA states this input symbol will allow us to visit from the current set of NFA states. To find this, we look at each one of the current NFA states and ask, 'Given this input symbol, where could it go next from here?' The answer is that it can follow any single edge labelled with that input symbol, as well as any number of ε edges. We search and find all nodes that we can reach in this manner, and add them to the set of nodes we can reach next. When this is done for all current NFA states, we'll have a set of NFA states corresponding to a particular DFA state, and we add an edge from the current DFA state to this state labelled with the input symbol.

Once we've followed this process for all DFA states and all symbols, our DFA will be complete. The resulting machines tracks what set of states the NFA is visiting at each moment in the input string. However, this machine is quite huge: since each set of NFA states may or may not contain any particular NFA state, there are 2ⁿ total such sets, and a DFA node for each of them. If we proceed like we did in the example, however, only creating nodes when we know they are needed, we can often create a much smaller DFA. Nevertheless, there are still cases for which we will need all 2ⁿ states; this is unavoidable.

[edit] Formal definition

Let M = (S, Σ, T, s, A) be a nondeterministic finite automaton.

Define the 5-tuple M_d = (S_d, Σ_d, T_d, s_d, A_d), where

• S_d = P(S)
• Σ_d = Σ
• s_d = C_ε(s)
• T_d(q, a) = C_ε( ∪_{∀ r ∈ q} T(r, a) )   ∀q ∈ S_d, ∀ a ∈ Σ
• A_d = {q | q ∈ S_d ∧ q ∩ A ≠ ∅}

P(S) is the powerset of S;

C_ε(q) is the ε-closure of q, i.e. the set of all states reachable from q by one or more ε-transitions.

It can be proved mathematically that M_d is a deterministic finite automaton that accepts the same language as M.

[edit] References

• Michael Sipser, Introduction to the Theory of Computation ISBN 0-534-94728-X. (See . Theorem 1.19, section 1.2, pg. 55.)
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-029880-X. (See chapter 2.)