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

The automaton is incomplete (5 states) and non-deterministic (3 states).
5 inputs 6 states 25 transitions
Inputs = { G0, G1, G2, G3, G17 }

0---1

000

----0

0-0-1

0-1-1

010

----0

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

0-1-0

1---1 0-0-0

001

0-0-1 1-0-1

011

0---1

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

1-0-1

0-0-1

1-1-1

101

1-0-1

1-1-1

1-1-1

1-0-1

1---1

100

Fig. 9.4 Graphical output of BALM showing the automaton s27 sup2.aut obtained by
changing the support of the automaton S27 sup1.aut

9.4 Determinizing

A non-deterministic automaton can be determinized using the subset construction
in which subset states are created if a transition input exists, which can transit to
at least two different states. Generally, the subset construction can lead to a set of
new states, which potentially can be any subset of the set of original states, leading
to a possible exponential number of states. In practice this almost never happens in
practical examples, and in fact the new automaton may have a smaller number of
states.

determinize -l S27_sup1.aut S27_sup1_det.aut

The result is the automaton S27 sup1 det.aut shown in Fig. 9.5 .
Note that the names of the states have changed to subset names (the option -l
keeps the original names to show which subset states were formed). For instance
state .This

came from the fact that S27 sup1.aut was non-deterministic, caused by having
restricted its support to only 3 of the original 5 inputs. Note that there are still only
a total of 6 states despite that a subset construction was done. This is because all
possible subset states cannot be reached from the initial state.

010 011 denotes a subset state composed of two states, 010 and 011