Hardware Reference
In-Depth Information
u
i
˛
i
W
u
i
2
B
?
;i
2
N
g
,the
f
u
1
˛
1
u
2
˛
2
:::
!
-expansion
of
L
to alphabet
B
(also called
B
-expansion of
L
)isthe
!
-language
L
*
!B
D[
˛
2
L
.˛/;
i.e., in order to expand
L
to
B
we insert all finite words over
B
before and after any
symbol
˛
i
of any word
˛
2
L
.
The generalization of the restriction operator from finitary languages to
!
-languages
is less straightforward because it must return an
!
-language, even when the words
of the initial
!
-language end with
!
-sequences of symbols only from alphabet
B
.
Definition 4.2.2.
Given the disjoint alphabets
A
and
B
,an
!
-language
L
defined
over
A
[
B;
, and the mapping
h
W
A
[
B
!
A
such that
h.a/
D
a
if
a
2
A
and
h.a/
D
if
a
62
A
(and by induction
h.˛/
D
h.˛
1
/h.˛
2
/:::h.˛
i
/:::
,
where
˛
D
˛
1
˛
2
:::˛
i
:::
2
L
), the
!
-restriction
of
L
to alphabet
A
(also called
A
-restriction of
L
)isthe
!
-language
;
L
.A
[
B/
?
B
!
if
L
+
!A
D
L
6
.A
[
B/
?
B
!
[
˛
2
L
n
.A
[
B/
?
B
!
h.˛/
if
The definition of
!
-restriction implies that if
L
D;
then
L
+
!A
D;
.
Proposition 4.14.
Given the disjoint alphabets
A
and
B
, and the
!
-language
L
A
!
,then
.L
*
!B
/
+
!A
D
L
.
Proposition 4.15.
Given the disjoint alphabets
A
and
B
, and the
!
-languages
L
1
.A
[
B/
!
,
L
2
.A
[
B/
!
such that
.L
2
+
!A
/
*
!B
D
L
2
,then
.L
1
\
L
2
/
+
!A
D
L
1
+
!A
\
L
2
+
!A
.
4.2.2
Parallel Composition of
!
-Languages
Definition 4.2.3.
Given the pairwise disjoint alphabets
I;U;V
and
O
,the
!
-
L
1
.I
[
U
[
V/
!
,
L
2
.O
[
U
[
V/
!
, and a subset
languages
E
I
[
V
[
O
,
the
!
-parallel composition
, denoted by
˘
!E
of
L
1
and
L
2
is the
!
-language
L
1
˘
!E
L
2
D
.L
1
*
O
\
L
2
*
I
/
+
E
:
We u s e
˘
E
or
˘
!
instead of
˘
!E
when the meaning is clear from the context. A
parallel composition models that the components interact by means of common
actions from
is executed if and only if both
components are ready to execute it at their current states, while external actions
from
U
[
V
, i.e., an action from
U
[
V
I
[
O
are executed independently.
L
0
2
L
2
,then
Proposition 4.16.
If
L
1
˘
!E
L
2
L
1
˘
!E
L
2
.
Search WWH ::
Custom Search