Implementation of Automata Manipulations - The Unknown Component Problem: Theory and Applications - page 107

subsetConstruction ( A, limit ) f
/* consider the case of a deterministic automaton */
if ( automaton A is deterministic )
return A;
/* initialize the STG to be extracted */
B = newAutomaton ();
/* get the initial state of the network */
I = getInitialState ( A );
/* initialize the set of subset states to be explored with the initial state */
S Df I g ;
/* explore states */
while ( S ¤; ) f
/* extract one subset state to be explored */
s = getOneState ( S ); S D S n s;
/* derive the transition relation of the given subset state */
R.i; x/ = deriveStateRelation ( A; s );
/* enumerate the next state subsets reachable from the given subset */
while ( R.i; x/ ¤; ) f
/* read one combination of variables in the relation */
minterm .i; x/ = getOneCombination ( R );
/* get the input minterm of this combination */
input .i / = 9 x minterm .i; x/;
/* get the subset of next states associated with this input */
n.x/ D9 i ŒR.i; x/ : input .i /;
/* get the transition predicate associated with this subset */
pred.i/ D8 x ŒR.i; x/ n.x/;
/* remove the predicate to this subset from the relation */
R.i; x/ D R.i; x/ : Š pred .i /;
/* if the next state subset is new, schedule it for exploration */
if ( stateIsNew (B; n)) f
S D S [ n;
/* set the acceptance attribute of the new product state */
if(subsetn contains at least one accepting state )
setAttribute ( n, “accepting” );
else
setAttribute ( n, “non-accepting” );
/* add transition from state s to state n under predicate pred */
addTransition ( B; s; n; pred );
/* quit if the number of states exceeds the limit */
if ( getNumStates .B/ limit )
return NULL;

return B;

g

Fig. 6.3 Determinization algorithm