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

state are assigned as transitions from that state to this don't-care state. Note that the
automata before and after completion both accept the same language. In BALM, an
incomplete automaton can be completed using command complete . By default,
this command adds a non-accepting don't-care state. In some applications, it is
necessary to add an accepting don't-care state, which is done using command
complete -a .
An automaton obtained from an FSM (by combining inputs and outputs) is
prefix-closed and input-progressive. Given an automaton A with the specification

of input and output variables, BALM is capable of trimming A to be the automaton

of an FSM.
An automaton A is prefix-closed if any prefix of an accepting string in L.A/ is

also in . A deterministic automaton can be trimmed to be prefix-closed by the

following three steps: (a) removing all non-accepting states and transitions into them
and from them, (b) removing states unreachable from the initial state, (c) completing
the resulting automaton. BALM provides command prefix to trim an automaton
to be prefix-closed.
A state of an automaton is progressive with respect to a set of variables

L.A/

U ,

called -progressive, if under any valuation of u at least one of its next states

is accepting. An automaton is progressive with respect to

U

U , if all of its states

are U -progressive. An automaton can be trimmed to be progressive with respect

to -progressive. BALM can trim an

automaton to be progressive by command progressive . The number of variables
that are to be considered as inputs to

U by iteratively deleting states that are not U

needs to be specified on the input line, e.g.,
progressive -i 5 specifies that the first 5 input variables of the automaton are
considered as inputs, the remaining as outputs. By convention, inputs must occur
first in the list of variables. Otherwise, command support can be used to reorder
the list.
Thus the command prefix; progressive can be used to convert a general
automaton into an FSM automaton (if one exists). In fact, progressive is defined
so that if the input automaton is not prefix-closed, it will be made prefix-closed
automatically. These operations will trim some states and transitions, so that the
result may not be a well-defined FSM, i.e., for every input minterm there exists a
next state. This can happen during language solving where we first derive the most
general solution automaton, from which we want to extract an FSM automaton. If
the trimming process results in a not well-defined FSM, then this implies that there
is no FSM solution. Also, BALM can further constrain the synthesized FSM to be
of Moore type. This may result in more trimming and also may lead to a not well-
defined machine.
In composing two FSMs, it is sometimes necessary to rearrange (rename,
reorder, create, or hide variables) input and output signals. BALM supports these
rearrangements by one command support .
In BALM, a deterministic finite automaton can be state-minimized using com-
mand minimize based on the Myhill-Nerode theorem [63]. In this, the full
behavior is preserved, just the number of states is reduced. In contrast, BALM
provides a heuristic algorithm (command dcmin ), which can be applied to a

U