The Software Package BALM - The Unknown Component Problem: Theory and Applications - page 137

Fig. 8.2 b. The transitions from this state to a next state are defined only for out =OK
and out=done , but not for out = notOK . As an automaton, it is incompletely
defined. When the automaton is completed it will have two states as shown in
Fig. 8.2 c, where state 2 is non-accepting.
Note that this is not exactly the same as the three-state automaton in Fig. 8.2 a,
because the two accepting states have been merged into one state. However, for
some applications, this can be done. For example, suppose that, when the fixed
part produces out = done or out = notOK , then no further changes in state
happen. Then it is not important what happens after states 2 or 3 in Fig. 8.2 are
entered. Thus, any transition added to state 3 in Structure 1 will be irrelevant. If
the transition is added, then state 3 becomes equivalent to state 1 and hence

Structure 1 can be minimized to that of Structure 2.
In summary, if the fixed part of the language solving problem has the property
that no state change occurs after a sink state is entered in the specification, then a
construct similar to that shown in Fig. 8.1 can be used to describe the specification
in BLIF-MV format. If, in addition, the fixed part is a deterministic FSM, then the
highly efficient method of Chap. 7 can be used to obtain the largest FSM solution.

3 ! 2

8.3 Two Alternate Synthesis Flows

BALM supports two different flows for solving language equations or manipulating
languages. The languages are represented in either BLIF-MV or AUT formats 3 .In
the former case it means that we start from a sequential circuit from which an STG
can be extracted, whereas in the latter case we start already from a given STG.

1. The first flow deals with FSMs where typically one has a fixed part F and

a specification given as FSMs. This flow is oriented towards solving for

the unknown component

S

. The same sequence of
operations could be done with the second type of flow using only AUT files,
but this FSM flow takes advantage of the special features of

X the equation F X S

to
provide a very efficient implementation, as discussed in detail in Chap. 7. The
entire flow is embodied in a single command, solve fsm equ , which produces
the largest FSM solution

F , S ,and X

X in AUT format. This command takes advantage of

the fact that F and S are deterministic FSM automata and X is required to be an

FSM automaton 4 .
2. The second flow deals directly with automata where each step consists of reading
in input AUT files, manipulating them according to the command, and writing

3 Notice that technically the AUT format is just a special case of the BLIF-MV format.
4 Precisely, the initial sequential circuits F and S yield deterministic FSMs whose automata define
the language equation for which we look for a solution that is an FSM automaton, i..e., a prefix-
closed input-progressive automaton.