Hardware Reference
In-Depth Information
3.3
Solution of FSM Equations Under Synchronous
Composition
3.3.1
Largest FSM Solution
Given alphabets I
1
;I
2
;U;V;O
1
;O
2
, an FSM M
A
over inputs I
1
V and outputs
U
O
1
, and an FSM M
C
over inputs I
1
I
2
and outputs O
1
O
2
, consider the
FSM equations
M
A
M
X
M
C
;
(3.1)
or,
M
A
M
X
Š
M
C
;
(3.2)
whose unknown is an FSM M
X
over inputs I
2
U and outputs V
O
2
. Sometimes
O
1
O
2
will be used.
9
the shortened notation I
D
I
1
I
2
and O
D
A variant of
equations is
Definition 3.3.1.
FSM M
B
is a
solution
of the equation M
A
M
X
M
C
,where
M
A
and M
C
are FSMs, iff M
A
M
B
M
C
.
FSM M
B
is a
solution
of the equation M
A
M
X
Š
M
C
,whereM
A
and M
C
are
FSMs, iff M
A
M
B
Š
M
C
.
Converting to the related FSM languages, we construct the associated language
equation
L.M
A
/
L.M
X
/
L.M
C
/;
(3.3)
where L.M
A
/ is an FSM language over alphabet I
1
U
V
O
1
, L.M
C
/ is an
FSM language over alphabet I
1
I
2
O
1
O
2
and the unknown FSM language is
over alphabet I
2
U
V
O
2
. The previous equation can be rewritten for simplicity
as
A
X
C:
(3.4)
We want to characterize the solutions of A
X
C as FSM languages. We know
from Theorem
2.12
that the largest solution of the equation A
X
C is the
language S
D
A
C .
When A and C are FSM languages, the following property holds.
Theorem 3.15.
Given the equation
A
X
C
and its largest solution
S
D
A
C
,
then
S
¤;
.
Proof.
FSM languages are not closed under complementation, because the com-
plement of an FSM lan
gu
age does not include the empty string
,
so it cannot be
an FSM language. So C does not include and neither does C
"
U
V
. Then the
9
Equations over more complex topologies and with respect to other input and output alphabets
can be solved similarly, by setting up the appropriate compositions, as pointed out already when
introducing composition of automata and FSMs.
Search WWH ::
Custom Search