Hardware Reference
In-Depth Information
Definition 3.4.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 (see Sect.
3.2.3
)
L.M
A
/
˘
L.M
X
/
L.M
C
/
[
.IO/
?
;
(3.7)
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
[
.IO/
?
:
(3.8)
We want to characterize the solutions of A
˘
X
C
[
.IO/
?
that are FSM languages.
We
know f
rom Theorem 2.16 t
hat the largest so
lution of the equation A
˘
X
C
[
.IO/
?
is the language S
D
A
˘
.C
\
.IO/
?
/.
In general S is not an FSM language. To compute the largest FSM language
contained in S ,thatisS
FSM
, we must compute the largest prefix-closed language
contained in S
\
..I
2
[
U /.V
[
O
2
//
?
.
Theorem 3.27.
Let
A
and
C
be FSM lang
uages. T
he largest FSM language that
is a solution of t
he equation
A
˘
X
is given by
S
FSM
,where
S
C
[
.IO/
?
D
D;
then
S
FSM
¤;
,
S
FSM
A
˘
.C
\
.IO/
?
/
.If
S
D;
;if
S
is obtained by
applying Proc
edure
3
.1.3
to
S
.If
S
FSM
D;
then the FSM language equation
A
˘
X
C
[
.IO/
?
has no solution.
Proof.
The first step of Procedure
3.1.3
computes the intersection of S with ..I
2
[
U /.V
[
O
2
//
?
to enforce that the solution, if it exists, is an FSM language with
input alphabet I
2
[
U and output alphabet V
[
O
2
.SinceA and C are regular
languages, S
\
..I
2
[
U /.V
[
O
2
//
?
is a regular language too and, by construction,
Procedure
3.1.3
extracts the largest FSM language contained in it.
t
Example 3.28.
Consider the FSMs M
A
Dh
S
A
;I
1
[
V; U
[
O
1
;T
A
;sa
i
and
M
C
Dh
S
C
;U;V;T
C
;s1
i
with S
A
Df
sa
g
, T
A
Df
.i; sa; sa; o
2
/, .
v
;sa;sa;
u
/
g
,
S
C
Df
s1
g
, T
C
Df
.i; s1; s1; o
1
/
g
. Th
e equation M
A
˘
M
X
M
C
yields the
language equation A
˘
X
C
[
.IO/
?
whose solution S becomes empty under
prefix-closure, because S does not contain , even though it contains the string
uv
.
Thus there is no solution.
By Proposition
3.7
, it is easy to derive an FSM M
S
FSM
associated to S
FSM
.This
allows us to talk about FSMs that are solutions of FSM equations, meaning any
reduction of the FSM M
S
FSM
, as guaranteed by Proposition
3.8
.
Example 3.29.
Consider the equation M
A
˘
M
X
M
C
, with the language of M
A
,
i.e., A
D
L
r
.M
A
/, and the language of M
C
, i.e., C
D
L
r
.M
C
/, represented by the
Search WWH ::
Custom Search