Let -move be the relation
. -reachable is the reflexive and
transitive closure of -move. Let -CLOSURE:
be a function which is defined as:

Furthermore, we write for the set .

For any given finite-state automaton
there
is an equivalent deterministic automaton
. *F*' is the set of all states in
2^{Q} containing a final state of *M*, i.e., the set of subsets
. *M*' has a single start state
*Q*_{0} which is the epsilon closure of the start states of *M*, i.e.,
. Finally,

An algorithm which computes *M*' for a given *M* will only need to
take into account states in 2^{Q} which are reachable from the start
state *Q*_{0}. This is the reason that for many input automata the
algorithm does not need to treat all subsets of states (but note that
there are automata for which all subsets are relevant, and hence
exponential behaviour cannot be avoided in general).

Consider the subset construction algorithm in figure 1.
The algorithm maintains a set of subsets * States*. Each subset can be
either marked or unmarked (to indicate whether the subset has been treated
by the algorithm); the set of unmarked subsets is sometimes referred to
as the agenda. The algorithm takes such an unmarked subset *T* and
computes all transitions leaving *T*. This computation is performed by
the function * instructions* and is called * instruction
computation* by [9].

The function * index_transitions* constructs the function
* transitions*:
which
returns for a given state *p* the set of pairs (*s*,*T*) representing
the transitions leaving *p*. Furthermore, the function * merge*
takes such a set of pairs and merges all pairs with the same first
element (by taking the union of the corresponding second elements).
For example:

The procedure * add* is responsible for `reachable-state-set
maintenance', by ensuring that target subsets are added to the
set of subsets if these subsets were not encountered before.
Moreover, if such a new subset contains a final state, then this
subset is added to the set of final states.