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