Manipulations of FSMs Represented as Sequential Circuits - The Unknown Component Problem: Theory and Applications - page 123

• Finally, in the complement of this product, which is the maximum solution,

the set of accepti ng states are DCA plus all the subset states which are left in
P . u ; v ;ns/ after Q has deleted all those that lead to DCN .

Thus all non-accepting subset states are mapped into DCN . As mentioned, this
can be done because we will make the answer prefix-closed , a requirement for
an FSM. (Thus, the X computed is the most general prefix-closed solution.) This
requirement increases efficiency, because during the subset construction, as soon
as a state of type .a; DC 1 / is encountered in a subset state, .cs/ , this state can be
replaced with DCN . This efficiently reduces the number of subset states that emanate
from such .cs/ . Further, those states that are trimmed immediately by this need not
be explored for reachability from them. This leads to a substantial trimming during
the subset construction. This trimming can be performed because S is prefix-closed,
and we require that X be prefix-closed also. 6
Similarly, the existence of the single state, DCA , derives from the fact that F

is prefix-closed. This allows for deferring the completion of F until the subset

construction.
Finally, to make X into an FSM automaton, it is made input-progressive. This
step is the same for both the monolithic and partitioned case and is not detailed here.
Note that in the partitioned flow, neither S nor F is made complete. In effect
such completion is deferred to the all-inclusive determinization step. The validity of
this is substantiated by the next section, which proves that the determinization and
completion operations commute and observes that completion also commutes with
complementation and product.

7.3 Completion and Determinization Commute

Theorem 7.2. To determinize a finite automaton A , the following two procedures
are equivalent:

1. Complete(Determinize ( A ), non-accepting)
2. Determinize(Complete ( A , non-accepting))

Proof. We show that these two procedures yield the same result by comparing
subset constructions without and with pre-completion. Let DC denote the added
non-accepting state. Recall that DC has a universal self-loop. It is clear that if
fs 1 ;:::;s k g is a subset state in the automaton constructed by Procedure 1, then
there must exist subset state fs 1 ;:::;s k g and/or fs 1 ;:::;s k ;DCg in the automaton
constructed by Procedure 2. Also, if subset state fs 1 ;:::;s k g or fs 1 ;:::;s k ;DCg

6 While this trimming can be substantial, there is no avoiding that subset construction can
be exponential. However, a common experience among people who have implemented subset
construction, is that it can be surprisingly efficient in practice, with relatively few subset states
reached, sometimes even leading to a reduction in the number of states.