Hardware Reference
In-Depth Information
3.2.2
Parallel Composition of FSMs
Consider the pair of FSMs
6
,
7
1. FSM M
A
has input alphabet I
1
[
V , output alphabet U
[
O
1
, and transition
relation T
A
.
2. FSM M
B
has input alphabet I
2
[
U , output alphabet V
[
O
2
, and transition
relation T
B
.
We define a parallel composition operator
˘
that associates a pair of FSMs M
A
and
M
B
with another FSM M
A
˘
M
B
such that:
1. The alphabet of the external inputs is I
1
[
I
2
D
I .
2. The alphabet of the external outputs is O
1
[
O
2
D
O.
Recall that, by definition of parallel composition of languages, a sequence ˛
2
..I
1
[
I
2
/.O
1
[
O
2
//
?
is in the language of the parallel composition of L.M
A
/ and
L.M
B
/ iff ˛ is in the restriction onto I
1
[
I
2
[
O
1
[
O
2
of the intersection of the
expansion of L.M
A
/ over I
2
[
O
2
and of the expansion of L.M
B
/ over I
1
[
O
1
:
˛
2
L.M
A
/
˘
L.M
B
/ iff
˛
2
ŒL.M
A
/
*
I
2
[
O
2
L
\
L.M
B
/
*
I
1
[
O
1
+
I
[
O
:
Notice that the expansions L.M
A
/
*
I
2
[
O
2
and L.M
B
/
*
I
1
[
O
1
are needed to have the
languages of M
A
and M
B
defined on the same alphabet; e.g., L.M
B
/ is defined over
I
2
[
U
[
V
[
O
2
, and the expansion
*
I
1
O
1
defines it over I
1
[
I
2
[
U
[
V
[
O
1
[
O
2
.
In this way we describe the behavior of each FSM as a component of the parallel
composition.
Lemma 3.13.
If
L.M
A
/
and
L.M
B
/
are FSM
[
-languages, then
L.M
A
/
˘
L.M
B
/
\
.IO/
?
is an FSM
[
-language.
Proof.
L.M
A
/
˘
L.M
B
/
\
.IO/
?
is IO-prefix-closed, because IO-prefix-closed
[
-languages are closed under
˘
composition. Indeed, a state of the finite automaton
corresponding to an FSM
[
-language is accepting iff it is the initial state or all its
ingoing edges are labeled by symbols in O. The property is preserved by intersection
and restriction over I
[
O. The intersection with .IO/
?
makes sure that in the
strings of the resulting FSM
[
-language an input is always followed by exactly
one output, so that a corresponding FSM (with edges labeled by pairs .i=o// can
be reconstructed. Notice that L.M
A
/
˘
L.M
B
/
\
.IO/
?
does not need to be IO-
progressive, because partial FSMs are allowed.
t
6
Notice that more complex topologies can be handled in the same way, by defining the composi-
tions with respect to the appropriate sets of variables, as remarked for synchronous composition.
7
For simplicity the alphabets I
1
;I
2
;O
1
;O
2
;U;V are assumed to be pairwise disjoint.
Search WWH ::
Custom Search