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, giving Θ() worst-case time complexity. 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; cf. picture for . Applications Brzozowski's algorithm for DFA minimization 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. References Further reading Finite automata