Hardware Reference
In-Depth Information
the non-accepting
DC
state. The complement of the output relation,
O.i; o; cs/
,
gives, for each current state,
cs
, all the input/output combinations, for which the
automaton's behavior is not defined, since a complete FSM is defined for all its
input combinations. When the partitioned representation is used, there is no need to
construct the monolithic representation of
O.i; o; cs/
. For any current state or subset
of current states, given by its characteristic function
.cs/
, its undefined input/output
combinations,
O
.i; o/
, can be found by an image computation followed by
complementation:
O
.i; o/ D 9
cs
O.i; o; cs/:.cs/:
This image can be efficiently computed using the partitioned representation of the
output relation:
O
.i; o/ D 9
cs
˘
j
Œo
j
O.i; o; cs/: .cs/:
7.2.1.2
Complementation (Deterministic Case)
In the general case of non-deterministic automata, determinization (subset construc-
tion) is required before complementation. In contrast, a deterministic automaton is
easily complemented by
in
terchanging the sets of its accepting and non-accepting
states. Thus computing
S
, which is deterministic, is easy. When an automaton
is derived from a deterministic multi-level network, its set of accepting states is
equal to the set of reachable states of the network. The
DC
state introduced
during completion is the only non-accepting state. In this case, complementation
is performed by changing the interpretation of the
DC
state: it becomes the only
accepting state, while all other states become non-accepting.
7.2.1.3
Product Computation
The product of two automata is defined when they have the same support. In
the partitioned view, having the same support simply means that each function is
considered as a function of the full set of variables. When the argument automata
are represented in their partitioned forms,
n
i;
v
;cs
F
;ns
j
T
F
o
T
j
T
F
;
and
n
i; cs
S
;ns
j
T
S
o
T
j
T
S
;
Search WWH ::
Custom Search