Powerset construction
Encyclopedia
In the theory of computation
and Automata theory
, 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 may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs.
The construction, sometimes called the Rabin–Scott powerset construction (or subset construction) to distinguish it from similar constructions for other types of automata, was first published by M. O. Rabin and Dana Scott
in 1959.
A state of the DFA is an accepting state if and only if at least one member of is an accepting state of the NFA.
In the simplest version of the powerset construction, the set of all states of the DFA is the powerset of , the set of all possible subsets of . However, many states of the resulting DFA may be useless as they may be unreachable from the initial state. An alternative version of the construction creates only the states that are actually reachable. For an NFA with ε-moves, the construction must be modified somewhat. In this case, the initial state consists of all NFA states reachable by ε-moves from , and the value of the transition function is the set of all states reachable by ε-moves from .
It is also possible for the NFA to have more than one initial state. In this case, the initial state of the corresponding DFA is the set of all initial states of the NFA, or (if the NFA also has ε-moves) the set of all states reachable from initial states by ε-moves.
The initial state of the DFA constructed from this NFA is the set of all NFA states that are reachable from state 1 by ε-moves; that is, it is the set {1,2,3}.
A transition from {1,2,3} by input symbol 0 must follow either the arrow from state 1 to state 2, or the arrow from state 3 to state 4. Additionally, neither state 2 nor state 4 have outgoing ε-moves. Therefore, ({1,2,3},0) = {2,4}, and by the same reasoning the full DFA constructed from the NFA is as shown below.
As can be seen in this example, there are five states reachable from the start state of the DFA; the remaining 11 sets in the powerset of the set of NFA states are not reachable.
uses the powerset construction, twice. It converts the input DFA into an NFA for the reverse language, by reversing all its arrows and exchanging the roles of initial and accepting states, converts the NFA back into a DFA using the powerset construction, and then repeats its process. Its worst-case complexity is exponential, unlike some other known DFA minimization algorithms, but in many examples it performs more quickly than its worst-case complexity would suggest.
Safra's construction, which converts a non-deterministic Büchi automaton
with states into a deterministic Muller automaton
or into a deterministic Rabin automaton with 2O( log ) states, uses the powerset construction as part of its machinery.
Theory of computation
In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...
and Automata theory
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
, the powerset construction or subset construction is a standard method for converting
Automata construction
In automata theory, automata construction is an important mathematical technique used to demonstrate the existence of an automaton with a certain desired property...
a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
. 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 may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs.
The construction, sometimes called the Rabin–Scott powerset construction (or subset construction) to distinguish it from similar constructions for other types of automata, was first published by M. O. Rabin and Dana Scott
Dana Scott
Dana Stewart Scott is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California...
in 1959.
Intuition
To simulate the operation of a DFA on a given input string, one needs to keep track of a single state at any time: the state that the automaton will reach after seeing a prefix of the input. However, to simulate an NFA, one needs to keep track of a set of states: all of the states that the automaton could reach after seeing the same prefix of the input, according to the nondeterministic choices made by the automaton. If, after a certain prefix of the input, a set of states can be reached, then after the next input symbol the set of reachable states is a deterministic function of and . Therefore, the sets of reachable NFA states play the same role in the NFA simulation as single DFA states play in the DFA simulation, and in fact the sets of NFA states appearing in this simulation may be re-interpreted as being states of a DFA.Construction
The powerset construction applies most directly to an NFA that does not allow state transformations without consuming input symbols (aka: "ε-moves"). Such an automaton may be defined as a 5-tuple , in which is the set of states, is the set of input symbols, is the transition function (mapping a state and an input symbol to a set of states), is the initial state, and is the set of accepting states. The corresponding DFA has states corresponding to subsets of . The initial state of the DFA is , the (one-element) set of initial states. The transition function of the DFA maps a state (representing a subset of ) and an input symbol to the set , the set of all states that can be reached by an -transition from a state in .A state of the DFA is an accepting state if and only if at least one member of is an accepting state of the NFA.
In the simplest version of the powerset construction, the set of all states of the DFA is the powerset of , the set of all possible subsets of . However, many states of the resulting DFA may be useless as they may be unreachable from the initial state. An alternative version of the construction creates only the states that are actually reachable. For an NFA with ε-moves, the construction must be modified somewhat. In this case, the initial state consists of all NFA states reachable by ε-moves from , and the value of the transition function is the set of all states reachable by ε-moves from .
It is also possible for the NFA to have more than one initial state. In this case, the initial state of the corresponding DFA is the set of all initial states of the NFA, or (if the NFA also has ε-moves) the set of all states reachable from initial states by ε-moves.
Example
The NFA below has four states; state 1 is initial, and states 3 and 4 are accepting. Its alphabet consists of the two symbols 0 and 1, and it has ε-moves. Its initial state is state 1.The initial state of the DFA constructed from this NFA is the set of all NFA states that are reachable from state 1 by ε-moves; that is, it is the set {1,2,3}.
A transition from {1,2,3} by input symbol 0 must follow either the arrow from state 1 to state 2, or the arrow from state 3 to state 4. Additionally, neither state 2 nor state 4 have outgoing ε-moves. Therefore, ({1,2,3},0) = {2,4}, and by the same reasoning the full DFA constructed from the NFA is as shown below.
As can be seen in this example, there are five states reachable from the start state of the DFA; the remaining 11 sets in the powerset of the set of NFA states are not reachable.
Complexity
Because the DFA states consist of sets of NFA states, an -state NFA may be converted to a DFA with at most states. For every , there exist -state NFAs such that every subset of states is reachable from the initial subset, so that the converted DFA has exactly states. A simple example requiring nearly this many states is the language of strings over the alphabet {0,1} in which there are at least characters, the th from last of which is 1. It can be represented by an -state NFA, but it requires DFA states, one for each -character suffix of the input.Applications
Brzozowski's algorithm for DFA minimizationDfa minimization
In computer science, more specifically in the branch of automata theory, DFA minimization is the task of transforming a given deterministic finite automaton into an equivalent DFA that has minimum number of states. Here, two DFAs are called equivalent if they describe the same regular language...
uses the powerset construction, twice. It converts the input DFA into an NFA for the reverse language, by reversing all its arrows and exchanging the roles of initial and accepting states, converts the NFA back into a DFA using the powerset construction, and then repeats its process. Its worst-case complexity is exponential, unlike some other known DFA minimization algorithms, but in many examples it performs more quickly than its worst-case complexity would suggest.
Safra's construction, which converts a non-deterministic Büchi automaton
Büchi automaton
In computer science and automata theory, a Büchi automaton is a type of ω-automaton, which extends a finite automaton to infinite inputs. It accepts an infinite input sequence iff there exists a run of the automaton that visits one of the final states infinitely often. Büchi automata recognize the...
with states into a deterministic Muller automaton
Muller automaton
In automata theory, a Muller automaton is a type of an ω-automaton.The acceptance condition separates a Muller automomaton from other ω-automata....
or into a deterministic Rabin automaton with 2O( log ) states, uses the powerset construction as part of its machinery.