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

Note that C.i; v ;cs/ can be represented as the sum of output non-conformance
conditions for each output. Therefore, the computation of Q . u ; v / can be done one
output at a time, without computing the monolithic relation for C.i; v ;cs/ .
Regarding the representation of states and subsets of states, the following facts
hold:
1. The original circuit uses logarithmic state encoding by means of state-bits.
2. During determinization, BDDs of state subsets are used as unique identifiers of
states after determinization.
3. After determinization, each state of the determinized automaton is represented
explicitly, without state encoding.

7.2.1.6 Validity of the Computation

The maximum prefix-closed solution (required for an FSM implementation) is
computed after determinization and completion, when the set of reachable subset
states, f.cs/g , are known and, for each of these, the function Q . u ; v / has been
computed, which defines the transitions from this subset state into a newly added
non-accepting state DCA .
To perform the complementation, which is the last step in computing the
maximum solution, the accepting and non-accepting states are switched. To do
this, we need to determine what the accepting states are after the previous steps
of computation. It is helpful to follow the computation process starting from the
initial automata, F and S , and consider the two types of their states: the accepting
states (labeled a ) and the non-accepting states.

• S could be completed by adding a new state DC 1 which would be its only non-

accepting state, because S is represented by the multi-level network and so is

pre fi x-closed.
•In S , DC 1 would be the only accepting state. (If S is non-deterministic, fDC 1 g

would be the only accepting (subset) state.)
•Since F was left incomplete an d is prefix-closed, all states of F are accepting.

• When forming the product F S , a product state is accepting only if both states

are accepting. Thus, in F S , the only accepting s tates would be those with labels
.a; DC 1 / , i.e., accepting in F and accepting in S .

• In the subset construction, a subset state is accepting if at least one product state

in the subset is accepting, i.e., of type .a; DC 1 / . If such occurs, then those
transitions represented by Q . u ; v / are redirected to DCN , since in the final
answer, these states are not accepting. 5 The new completion state, DCA , added
after the sub se t construction to complete it, is non-accepting for the determinized
product F S , but accepting in the final answer.

5 Note that it is not necessary to compute subset states which emanate from such a state since once
reached, we know that all input sequences with this prefix are not in the language of an FSM.