Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Powerset construction
open-in-new
<p>In the <a href="/facts/Theory_of_computation/xYJd2YeI">theory of computation</a> and <a href="/facts/Automata_theory/Q6BmPv63">automata theory</a>, the powerset construction or subset construction is a standard method for converting a <a href="/facts/Nondeterministic_finite_automaton/fW600oAl">nondeterministic finite automaton</a> (NFA) into a <a href="/facts/Deterministic_finite_automaton/9conRLFS">deterministic finite automaton</a> (DFA) which recognizes the same <a href="/facts/Formal_language/crDTyP8q">formal language</a>. 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 <i>n</i> states, the resulting DFA may have up to 2<i>n</i> states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs. </p><p>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 <a href="/facts/Michael_O._Rabin/M6NHIb5J">Michael O. Rabin</a> and <a href="/facts/Dana_Scott/XEVddlVg">Dana Scott</a> in 1959. </p>