Hardware Reference
In-Depth Information
Problems
3.1.
Consider
the
FSMs
and
their
parallel
composition
shown
textually
in
Example
3.14
(a).
Compute all the steps to verify the correctness of the composition.
(a) Derive from M
A
and M
B
the automata A and B recognizing, respectively, the
languages L
r
.M
A
/ and L
r
.M
B
/.
(b) Compute the automaton B
*
I
1
[
O
1
.
(c) Compute the automaton A
\
B
*
I
1
[
O
1
.
(d) Compute the automaton .A
\
B
*
I
1
[
O
1
/
+
I
1
[
O
1
\
.I
1
O
1
/
?
.
(e) Extract the FSM M
A
˘
M
B
from the automaton in the previous step and mini-
mize it. The result should coincide with the one proposed in Example
3.14
(a).
3.2.
Repeat the steps of Problem
3.1
for the variant reported in Example
3.14
(b).
3.3.
Consider the examples of synchronous composition shown in Fig.
3.1
.Forin-
stance, the picture shows machines M
A
and M
B
and their synchronous composition
M
A
B
D
M
A
M
B
. What are the other machines such that their composition with
the context M
A
yields the same composed machine M
A
B
?
Compute all such machines by solving the equation M
A
M
X
D
M
A
B
. What is the
relation between the largest solution of the equation and the given machine M
B
?
3.4.
Consider the traffic controller example described in [12] and already intro-
duced in Problem 2.1.
Interpret the state graphs in Figs. 2.10 and 2.11 as respectively the context FSM
M
A
and the specification FSM M
C
, by defining their input and output variables
as follows. The inputs of M
A
are two binary variables
v
1
;
v
2
, and its output is the
multi-valued variable
colours
that can assume the values
green, red, yellow
.The
inputs of M
C
are two multi-valued variables i
1
;i
2
that can assume each one of the
three values 1; 2; 3, its output is again the multi-valued variable
colours
.
Find the largest solution of the equation M
A
M
X
M
C
, where the input
variables of M
X
are i
1
;i
2
and its output variables are
v
1
;
v
2
. This is a series topology
where M
X
feeds M
A
, and the composition of M
X
and M
A
yields M
C
.
Repeat the problem assuming that M
X
has one more input: the variable
colours
produced by M
A
, as in the controller's topology.
3.5.
Consider the FSMs M
A
Dh
S
A
;V;U;T
A
;sa
i
and M
C
Dh
S
C
;I;O;T
C
;s1
i
with S
A
Df
sa; sb
g
, T
A
Df
.
v
1; sa; sb;
u
1/, .
v
2: sa; sa;
u
1/, .
v
1; sb; sa;
u
1/,
.
v
2; sb; sb;
u
2/,andS
C
Df
s1; s2; s3
g
, T
C
Df
.i1; s1; s2; o1/, .i 2; s1; s1; o2/,
.i1; s2; s3; o2/, .i 2; s2; s3; o1/
g
, .i 2; s3; s3; o1/, .i1; s3; s1; o2/.
Compute the largest solution of the equation M
A
M
X
M
C
,whereM
X
has
inputs I
U and outputs V
O. Notice that in this example only M
X
has access
to the environment.
3.6.
Consider the FSMs M
A
Dh
S
A
;V;O;T
A
;sa
i
and M
C
Dh
S
C
;I;O;T
C
;s1
i
with S
A
Df
sa; sb
g
, T
A
Df
.
v
1; sa; sb; o1/, .
v
2: sa; sb; o2/, .
v
1; sb; sa; o2/,
Search WWH ::
Custom Search