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

product after hiding, while leaving F incomplete leads to a deterministic product
after hiding. Thus a subset construction is avoided when F is not completed.
Of course, computing the CSF is only one step in sequential synthesis. Finding
an optimum sub-solution of the CSF remains an outstanding problem for future
research.
Problems
7.1. Representing Automata by MV Networks
Manipulation of finite automata is performed using the graph representation, as
discussed in Chap. 6.
However automata can also be represented and manipulated using multi-valued
multi-level networks that implement the next-state logic F , the latches (one or more
multi-valued latches according to the encoding) and the acceptance unction Acc .
F is the next-state logic that depends on the inputs and present-state variables and
produces the next-state variables. If the automaton is non-deterministic F too is non-
deterministic. Acc is a binary node producing value 1 if and only if the present-state
is accepting; it depends only on the present-state. In practice we restrict ourselves
to representing deterministic automata, because non-deterministic ones introduce
complications 7 in the network representation.
Describe how to represent automata by MV networks. Discuss the various
options for encoding and logic optimization algorithms.
Note that the unused codes should be stored in a specific network, call it EXDC
(external don't cares) network, and exploited as such when appropriate. The EXDC
network must be updated when the latches change.
7.2. Manipulating Automata by MV Networks
In Problem 7.1 we represented a deterministic automaton by a MV network with
multiple latches.
Once an automaton is encoded as a network, the next task is to express the
following operations on automata as operations on MV networks, i.e., to provide
algorithms that perform these operations by working directly on the data structures
representing the MV networks:
(a) Operation complement of an automaton.
(b) Operation product of two automata.
(c) Operation variable projection of an automaton.
(d) Operation determinization of an automaton.
7 Say that an MV network has two binary latches and that under some input both latches produce
both 1 and 0. Does this situation correspond to the subset of states .00; 11/ ,or .01; 10/ or
.00; 11; 10/ ? To avoid loss of information we should introduce additional input variables to
distinguish the situations. This is an unexplored area of synthesis.