# Powerset construction

## Method for making finite automata deterministic / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Powerset construction?

Summarize this article for a 10 years old

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 2^{n} 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 Michael O. Rabin and Dana Scott in 1959.[1]