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. NFA with ε-moves For an NFA with ε-moves (also called an ε-NFA), the construction must be modified to deal with these by computing the ε-closure of states: the set of all states reachable from some given state using only ε-moves. Van Noord recognizes three possible ways of incorporating this closure computation in the powerset construction: Compute the ε-closure of the entire automaton as a preprocessing step, producing an equivalent NFA without ε-moves, then apply the regular powerset construction. This version, also discussed by Hopcroft and Ullman, is straightforward to implement, but impractical for automata with large numbers of ε-moves, as commonly arise in natural language processing application. During the powerset computation, compute the ε-closure of each state that is considered by the algorithm (and cache the result). During the powerset computation, compute the ε-closure of each subset of states that is considered by the algorithm, and add its elements to . Multiple initial states If NFAs are defined to allow for multiple initial states, 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. 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