Next: Variants for -Moves Up: Subset Construction Previous: Subset Construction

## Problem statement

Let a finite-state machine M be specified by a tuple where Q is a finite set of states, is a finite alphabet, is a function from . Furthermore, is a set of start states and is a set of final states. 3

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 2Q containing a final state of M, i.e., the set of subsets . M' has a single start state Q0 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 2Q which are reachable from the start state Q0. 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).

Figure 1: Subset-construction algorithm.

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.

Next: Variants for -Moves Up: Subset Construction Previous: Subset Construction

2000-07-10