Fundamental Operations in BALM - The Unknown Component Problem: Theory and Applications - page 151

completion don't care state. The incompleteness is due to the output of the FSM
becoming an input to the automaton, because by construction the inputs of the
automaton are the cartesian product of the inputs and outputs of the FSM. The result
is that a state of the automaton is not complete for those combinations of values of
inputs and outputs of FSM such that at that state the FSM under those inputs does
not produce those outputs.

9.2 Completing an Automaton

A state is called incomplete if under some input combinations no transition to a next
state is defined. If an automaton has some incomplete states, it can be completed by
adding one additional non-accepting state, called the don't care state.
complete S27.aut S27_cpl.aut
The result is the automaton S27 cpl.aut shown in Fig. 9.2 .
Since this example came from an FSM, all states are accepting except the
completion don't care state

. Note that it is shaded differently to indicate a non-
accepting state. Also note that there are 6 incoming transitions to

DC

DC (besides its

universal self-loop), one from each state.

The automaton is complete and deterministic.
5 inputs 7 states 32 transitions
Inputs = { G0, G1, G2, G3, G17 }

00-01
011-1 000

-0-10

-0-10
0-1-0
00--0

010

010-1 0-1-1

10-01
111-1

0-1-0 0-1-1

00--1

010-0

10-01
111-1

011

110-1

001

0-0-0 0-0-1 0-1-1

---00
-1--0
-0-11

1-1-1 110-1 010-1 1-1-1

0---1
1--00
11--0
-0-11

1-1-1
10--1

1-0-1

100

0-0-1 1-0-1

1---0
0---1

1-1-1 110-1 ----0

101

1-0-1 ----0

----0

DC

-----

Fig. 9.2 Graphical output of BALM showing the automaton S27 cpl.aut obtained by

completing the automaton S27.aut