Hardware Reference
In-Depth Information
an internal hidden alphabet, and thus the composed FSMs
M F M D
and
M F M E
are specified over input alphabet
, respectively.
By solving the system of equations (see next section), one finds the largest
solution in Fig. 12.6 d whose reduction to a single state in Fig. 12.6 e can replace
the FSM
I
and output alphabets
Z
and
Y
M F
without changing the overall behavior of the composition.
In the next section we discuss some facts about solving systems of FSM
equations.
12.3
Solving a System of FSM Equations
We refer to Definition 12.2.1 of a system of FSM equations. An FSM
M B is a
solution of a system of FSM equations if it is a solution of each equation of the
system. The largest solution
M S of a system of FSM equations contains every
solution of the system, i.e., it is such that every solution of the system of equations
is a reduction of the FSM
M S . Therefore the largest solution of a system of
FSM equations can be obtained as the intersection of the largest solutions over all
equations of the system. The intersection of FSMs is defined in a number of papers;
we use the definition from [147].
Definition 12.3.1. Given two nondeterministic FSMs
M 1 D .S 1 ;I;O;T 1 ;r 1 /
and
M 2 D .S 2 ;I;O;T 2 ;r 2 /
,the intersection of FSMs
M 1
and
M 2 , denoted by
M 1 \
M 2 , is the largest connected submachine of the FSM
.S 1 S 2 ;I;O;T \ ;.r 1 ;r 2 //
,
where
..s 1 ;s 2 /; i; o; .s 1 ;s 2 // 2 T \ , Œ.s 1 ;i;o;s 1 / 2 T 1 ^ .s 2 ;i;o;s 2 / 2 T 2 :
The definition can be easily extended to more than two machines.
If FSMs
M 2 are observable then their intersection is also an observable
FSM. However, the intersection of complete FSMs can be a partial FSM. In order
to describe the set of all complete machines that are reductions of
M 1
and
M 2
simultaneously, we need the notion of the largest complete submachine of the
intersection. The largest complete submachine Complete
M 1
and
M A is
obtained by deleting iteratively all the states with undefined transitions. If the initial
state is deleted then
.M A /
of the FSM
M A has no complete submachine. Otherwise, the obtained
complete machine is the largest complete submachine of
M A . The set of complete
reductions of
coincide, and as a corollary, the following
statement holds for the intersection of two observable FSMs [147].
M A
and of Complete
.M A /
Proposition 12.6. Given two observable FSMs
M A
and
M B , a complete FSM
is a reduction of both FSMs
M A
and
M B , if and only if it is a reduction of
Complete
.A \ B/
, where Complete
.A \ B/
is the largest complete submachine of
the intersection
M A \ M B .
Search WWH ::




Custom Search