Hardware Reference
In-Depth Information
Any language L
.
IU
?
O/
?
is U -deadlock-free (because no word ending by a
symbol
u
2
U belongs to the language).
Example 2.10.
(a) Let X
D
I
[
O, I
Df
i
1
;i
2
g
, O
Df
o
1
;o
2
g
and U
Df
u
1
;
u
2
g
.The
language L
Df
.i
1
.
u
1
u
2
u
1
/
?
o
1
/
?
C
.i
1
.
u
1
u
2
u
1
/
?
o
1
/
?
i
1
u
1
u
2
g
is U -deadlock-free,
because any word in the language terminating by
u
1
or
u
2
can be extended
by suffix
u
1
to a word in the language terminating by o
1
. The corresponding
automaton is shown in Fig.
2.1
c.
(b) Let X
D
I
[
O, I
Df
i
1
;i
2
g
, O
Df
o
1
;o
2
g
and U
Df
u
1
;
u
2
;
u
3
g
. The language
L
Df
i
1
.
u
1
u
2
u
3
/
?
o
1
/
?
C
.i
1
.
u
1
u
2
u
3
/
?
o
1
/
?
i
1
u
1
u
2
C
.i
1
.
u
1
u
2
u
3
/
?
o
1
/
?
i
1
u
1
u
2
u
1
u
2
g
is not U -deadlock-free, since the words in the collection
f
.i
1
.
u
1
u
2
u
3
/
?
o
1
/
?
i
1
u
1
u
2
u
1
u
2
g
cannot be extended to words in L (e.g., ˛
D
i
1
u
1
u
2
u
1
). The corre-
sponding automaton is shown in Fig.
2.1
d.
Definition 2.1.13.
A language L
¤;
over alphabet X
[
U (X and U disjoint) is
X
?
the language ˛
*
U
U
-convergent
if
8
˛
2
\
L is finite, otherwise it is
U
-divergent
.
Df
i
u
?
o
g
Example 2.11.
The language L
where X
Df
i; o
g
and U
Df
u
g
is
U -divergent, as witnessed by the string ˛
D
io
2
X whose expansion includes
f
iu
?
o
g
f
˛
*
U
gDf
.
io
/
*f
u
g
gDf
u
?
iu
?
ou
?
the infinite set
coinciding with L:
g
f
iu
?
o
gD
L.
2.1.4
Composition of Languages
Consider two systems A and B with associated languages L.A/ and L.B/.The
systems communicate with each other by a channel U and with the environment
by channels I and O. We introduce two composition operators that describe the
external behavior of the composition of L.A/ and L.B/.
Definition 2.1.14.
Given the pairwise disjoint alphabets I; U; O, language L
1
over
I
U and language L
2
over U
O,the
synchronous composition
of languages L
1
and L
2
is the language
3
Œ.L
1
/
"
O
\
.L
2
/
"
I
#
I
O
, denoted by L
1
I
O
L
2
,defined
over I
O.
Definition 2.1.15.
Given the pairwise disjoint alphabets I; U; O, language L
1
over
I
[
U and language L
2
over U
[
O,the
parallel composition
of languages L
1
and
L
2
is the language Œ.L
1
/
*
O
\
.L
2
/
*
I
+
I
[
O
, denoted by L
1
˘
I
[
O
L
2
, defined over
I
[
O.
Given alphabets I; U; O, language L
1
over I
[
U and language L
2
over U
[
O,
the l
-bounded parallel composition
of languages L
1
and L
2
is the language
Œ.L
1
/
*
O
[
O/
?
\
.L
2
/
*
I
\
.I
*
.U;l/
+
I
[
O
, denoted by L
1
˘
l
I
[
O
L
2
, defined over
I
[
O.
3
Use the same order I
U
O in the languages .L
1
/
"
O
and .L
2
/
"
I
.
Search WWH ::
Custom Search