Hardware Reference
In-Depth Information
a
b
c
d
Fig. 2.1
(
a
) Finite automaton of the language described in Example
2.9
-a; (
b
) Finite automaton
of the language described in Example
2.9
-b; (
c
) Finite automaton of the language described in
Example
2.10
-a; (
d
) Finite automaton of the language described in Example
2.10
-b
Example 2.9.
(a) Let I
Df
i
1
;i
2
g
, O
Df
o
1
;o
2
g
and U
Df
u
1
;
u
2
g
. The language
g
is UI
?
O-progressive, since any word in L
can be extended to a word in L by suffixes starting with either i
1
or i
2
.The
corresponding automaton is shown in Fig.
2.1
a.
(b) Let I
Df
.i
1
u
1
u
2
u
1
o
1
i
2
u
1
o
2
/
?
L
C
Df
.i
1
o
1
/
?
Df
i
1
;i
2
g
, O
Df
o
1
;o
2
g
and U
Df
u
1
g
. The language L
C
.i
1
o
1
/
?
i
2
u
1
o
2
.i
1
u
1
o
2
/
?
is not
IU
?
O-progressive, since the words in the set
g
g
are in L,butwheni
D
i
2
there is no ˇ
2
U
?
and no o
2
O
such that ˛i
2
ˇo
2
L (e.g., ˛
D
i
2
u
1
o
2
cannot be extended by any suffix starting
with i
2
). The corresponding automaton is shown in Fig.
2.1
b.
Definition 2.1.11.
A language L over alphabet I
f
i
2
u
1
o
2
.i
1
u
1
o
2
/
?
[
O (I and O disjoint) is
I
+
-defined
if L
+
I
D
I
?
.
An
IO
-progressive language is I
+
-defined, so is an
IU
?
O-progressive language, but
the converse does not hold.
Definition 2.1.12.
A language L
¤;
over alphabet X
[
U (X and U disjoint) is
U
-deadlock-free
if
8
˛
2
.X
[
U/
?
9
ˇ
2
U
?
8
u
2
U
9
x
2
XŒ˛
u
2
L
)
˛
u
ˇx
2
L:
Search WWH ::
Custom Search