Hardware Reference
In-Depth Information
intersection A
"
I
2
O
2
\
C
"
U
V
does not include the empty string,
neither
does its
projection .A
"
I
2
O
2
\
C
"
U
V
/
#
I
2
U
V
O
2
,thatisA
C . Therefore A
C includes
the empty string, i.e.,
2
S
¤;
.
t
Example 3.16.
Consider the FSMs M
A
Dh
S
A
;I
1
V; U
O
1
;T
A
;sa
i
and M
C
D
h
S
C
;U;V;T
C
;s1
i
with S
A
Df
sa
g
, T
A
Df
.01; sa; sa; 01/, .00; sa; sa; 01/,
.11; sa; sa; 10/, .10; sa; sa; 10/
g
, S
C
Df
s1
g
, T
C
Df
.1;s1;s1;1/,
.0;s1;s1;0/
g
. The equation M
A
M
X
M
C
yields the language equation
A
X
C with solution S
Df
g
, i.e., the corresponding FSM solution M
X
produces only the empty word. The reason is that the i=o combinations of M
C
,i.e.,
1=1; 0=0 do not match any i=o combination of M
A
, i.e., 0=1; 1=0.
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 .
Theorem 3.17.
Let
A
and
C
be FSM languages. The largest FSM l
anguag
e that is
a solution of the equation
A
X
C
is given by
S
FSM
,where
S
D
A
C
.
S
FSM
is
obtained by applying Procedure
3.1.1
to
S
.
S
FSM
contains at least the string
.
If
A
S
FSM
D
C
then
S
FSM
is the largest solution of the FSM language equation
A
X
D
C
.
Thus, the synchronous FSM language equation A
X
C is always solvable, since
the solution includes at least the empty string and so its prefix-closure does too. In
other words, the trivial FSM is always a solution of the synchronous FSM equation
A
X
C .
Example 3.18.
Consider the equation M
A
M
X
M
C
, with M
A
and M
C
shown,
respectively, in Fig.
3.4
a,c. The FSMs are composed with respect to the rectification
topology and their alphabets are I
1
Df
i
1
;i
2
g
, O
1
Df
o
1
;o
2
g
, U
Df
u
1
;
u
2
g
and
V
Df
v
1
;
v
2
g
. M
A
is a partial FSM, e.g., the transitions from state a under inputs i
1
v
2
and i
2
v
2
are missing. The automata of the related languages are shown, respectively,
in Fig.
3.4
b,d. The intermediate steps to compute the solution are demonstrated
in Fig.
3.4
e-g. The
automaton generating the largest language solution, S
D
.A
\
.C
"
U
[
V
/
#
U
[
V
, is portrayed in Fig.
3.4
h. The state labeled dc accepts strings
that are not in the language of the context. Notice that S is not prefix-closed, since
string
u
1
v
1
u
2
v
1
2
S ,but
u
1
v
1
62
S ; its largest prefix-closed sublanguage yields the
largest FSM solution M
X
showninFig.
3.4
i. M
X
is a PNDFSM and the composition
of any DFSM reduction of M
X
with M
A
produces the trivial machine.
Example 3.19.
Consider the following variants of the context FSM M
A
in the
equation M
A
M
X
M
C
, studied in Example
3.18
. The specification FSM
M
C
is the same. The variants of M
A
are M
A
, M
A
and M
A
, shown respectively
in Fig.
3.5
a,d,f. They are all complete FSMs, whereas M
A
of Example
3.18
is a
partial FSM. The solution of M
A
M
X
M
C
is M
X
in Fig.
3.5
c. M
X
is a partial
FSM and M
A
M
X
D
M
, i.e., the composition yields the trivial FSM that is the
“ultimate” partial machine, because each external input sequence causes a violation
Search WWH ::
Custom Search