Hardware Reference
In-Depth Information
In this way we describe the behavior of each FSM as a component of the
synchronous composition.
Lemma 3.10.
If
L.M
A
/
and
L.M
B
/
are FSM
-languages, then
L.M
A
/
L.M
B
/
is an FSM
-language.
Proof.
L.M
A
/
L.M
B
/ is prefix-closed, because prefix-closed FSM
-languages
are closed under
composition. Notice that L.M
A
/
L.M
B
/ does not need to be
progressive, because partial FSMs are allowed.
t
Therefore we can state the following definition.
Definition 3.2.1.
The
synchronous composition of FSMs
M
A
and M
B
yields the
FSM M
A
M
B
with language
L.M
A
M
B
/
D
L.M
A
/
L.M
B
/:
If the language L.M
A
/
L.M
B
/
Df
g
,thenM
A
M
B
is a trivial FSM.
The previous definition is sound because the language L.M
A
/
L.M
B
/ by
Lemma
3.10
is an FSM language, which corresponds to a (partial) complete FSM if
the language L.M
A
/
L.M
B
/ is (not) I -progressive. Then by subset construction
and state minimization, we produce a reduced observable FSM. In summary, we
convert from the FSMs M
A
and M
B
to the automata accepting their FSM languages,
operate on them and then convert back from the resulting automaton to an FSM;
then we produce a reduced PNDFSM (we assume that M
A
and M
B
are PNDFSMs),
because subset construction determinizes the underlying finite automaton.
Example 3.11.
(a) Synchronous composition of two FSMs defining a complete
FSM.
Given the topology shown in Fig. 1.1d, consider the FSMs M
A
Dh
S
A
;I
1
V; U
O
1
;T
A
;s1
i
and M
B
Dh
S
B
;U;V;T
B
;sa
i
with S
A
Df
s1; s2; s3
g
,
T
A
Df
.
1-
; s1; s1; 11/, .00: s1; s2; 10/, .01; s1; s3; 10/, .
-0
;s2;s1;01/,
.
-1
;s2;s3;10/, .
-1
; s3; s1; 01/, .
-0
; s3; s2; 00/
g
, S
B
Df
sa; sb
g
,
T
B
Df
.0; sa; sa; 1/, .1;sa;sb;0/, .0; sb; sa; 0/, .1; sb; sb; 0/
g
.
5
Then M
A
M
B
D
M
A
B
Dh
S
A
B
;I
1
;O
1
;T
A
B
;.s1;sa/
i
with S
A
B
D
f
.s1; sa/,.s1; sb/,.s2; sb/
g
and T
A
B
Df
.1; .s1; sa/; .s1; sb/; 1/, .0; .s1; sa/;
.s2; sb/; 0/, .1; .s1; sb/; .s1; sb/; 1/ .0; .s1; sb/; .s2; sb/; 0/, .
-
;.s2;sb/;
.s1; sa/; 1/
g
is a complete FSM.
Figure
3.1
shows FSMs M
A
, M
B
and M
A
M
B
.
(b) Synchronous composition of two FSMs defining a partial FSM.
Modify the transition relation of M
B
to obtain M
B
as follows: T
B
D
f
.0; sa; sa; 1/, .1 sa sb 0/, .0; sb; sa; 1/, .1; sb; sb; 0/
g
.ThenT
A
B
0
D
f
.1; .s1; sa/; .s1; sb/; 1/, .0; .s1;sa/; .s2;sb/; 0/, .1; .s1; sb/; .s1; sb/; 1/
5
denotes input or output don't care conditions.
Search WWH ::
Custom Search