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