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

completeAutomaton ( A ) f
/* iterate over states and check if there are incomplete states */
/* cond.i/ s ! t is the predicate over input variables i */
/* of the transition from state s to state t */
complete D 1;
for each state s of automaton A f
sum .i / D 0;
for each transition t from state s
sum .i / D sum .i / C cond.i/ s ! t
if ( sum .i / ¤ 1 ) f
complete D 0;
break;

g
if ( complete )
return;
/* create the non-accepting state na */
addState ( A, na );
/* iterate over states and add transitions from
the incomplete states into the non-accepting state na */
for each state s of automaton A f
sum .i / D 0;
for each transition t from state s
sum .i / D sum .i / C cond .i / s ! t
if ( sum .i / D 1 )
continue;
addTransition ( A; s; na; Š sum .i / );

g

g

Fig. 6.2 Completion algorithm

getOneCombination : Extracts one minterm .m i ;m o ;m x / from the BDD.
stateIsNew : Checks if the state m x is already in the STG.
addTransition : Adds one transition to the STG.
getNumStates : Queries STG for its number of states.

6.2.2 Completion

A finite automaton is complete if the Boolean OR of input predicates of all
transitions from each state evaluates to constant 1. If there exists at least one state,
for which this predicate does not hold, the automaton is incomplete. The pseudo-
code in Fig. 6.2 contains the pseudo-code of the completion algorithm.