Hardware Reference
In-Depth Information
Proposition 2.2.
The following equivalences hold.
(a) Given alphabets
X
and
Y
, a language
L
over alphabet
X
, and a string
˛
2
.X
Y/
?
,then
˛
#
X
2
L
,
˛
2
L
"
Y
.
(b) Given disjoint alphabets
X
and
Y
, a language
L
over alphabet
X
, and a string
˛
2
.X
[
Y/
?
,then
˛
+
X
2
L
,
˛
2
L
*
Y
.
Proposition 2.3.
The following distributive laws for
"
and
#
hold.
(a) Let
L
1
;L
2
be languages over alphabet
U
.Then
"
commutes with
[
.L
1
[
L
2
/
"
I
D
L
1
[
L
2
"
I
:
"
I
(b) Let
L
1
;L
2
be languages over alphabet
U
.Then
"
commutes with
\
.L
1
\
L
2
/
"
I
D
L
1
\
L
2
"
I
:
"
I
(c) Let
M
1
;M
2
be languages over alphabet
I
U
.Then
#
commutes with
[
.M
1
[
M
2
/
#
U
D
M
1
[
M
2
#
U
:
#
U
(d) Let
M
1
;M
2
be languages over alphabet
I
U
.If
M
2
D
.M
2
#
U
/
"
I
(or
M
1
D
.M
1
#
U
/
"
I
), then
#
commutes with
\
.M
1
\
M
2
/
#
U
D
M
1
\
M
2
#
U
:
#
U
Proof.
Thesis: .L
1
\
L
2
/
"
I
D
L
1
\
L
2
"
I
.
"
I
(
)
) If the string .i
1
;
u
1
/:::.i
k
;
u
k
/
2
\
2
\
.L
1
L
2
/
"
I
,then
u
1
:::
u
k
L
1
2
2
2
L
2
; thus
u
1
:::
u
k
L
1
,
u
1
:::
u
k
L
2
,andso.i
1
;
u
1
/:::.i
k
;
u
k
/
L
1
"
I
,
.i
1
;
u
1
/:::.i
k
;
u
k
/
2
L
2
"
I
, implying .i
1
;
u
1
/:::.i
k
;
u
k
/
2
L
1
\
L
2
"
I
.
"
I
(
(
) If the string .i
1
;
u
1
/:::.i
k
;
u
k
/
2
\
L
2
2
L
1
"
I
,then.i
1
;
u
1
/:::.i
k
;
u
k
/
"
I
2
2
2
L
1
"
I
, .i
1
;
u
1
/:::.i
k
;
u
k
/
L
2
"
I
; thus
u
1
:::
u
k
L
1
,
u
1
:::
u
k
L
2
, implying
u
1
:::
u
k
2
L
1
\
L
2
,andso.i
1
;
u
1
/:::.i
k
;
u
k
/
2
.L
1
\
L
2
/
"
I
.
Similarly one proves the first and third identity involving
[
.
Thesis: If M
2
D
D
\
D
.M
2
#
U
/
"
I
(or M
1
.M
1
#
U
/
"
I
), then .M
1
M
2
/
#
U
M
1
#
U
\
M
2
#
U
.
(
)
) If the string
u
1
:::
u
k
2
.M
1
\
M
2
/
#
U
then there exists i
1
:::i
k
such that
2
M
1
\
M
2
, i.e., .i
1
;
u
1
/:::.i
k
;
u
k
/
2
2
.i
1
;
u
1
/:::.i
k
;
u
k
/
M
1
, .i
1
;
u
1
/:::.i
k
;
u
k
/
2
M
1
2
M
2
M
2
,andso
u
1
:::
u
k
and
u
1
:::
u
k
#
U
.
#
U
(
(
) If the string
u
1
:::
u
k
2
\
2
M
1
M
2
#
U
,i.e.,
u
1
:::
u
k
M
1
and
#
U
#
U
2
2
u
1
:::
u
k
M
2
#
U
, then there exists i
1
:::i
k
such that .i
1
;
u
1
/:::.i
k
;
u
k
/
M
1
.
D
2
Moreover, since M
2
.M
2
#
U
/
"
I
, from
u
1
:::
u
k
M
2
it follows that
#
U
2
2
.i
1
;
u
1
/:::.i
k
;
u
k
/
M
2
. In summary, .i
1
;
u
1
/:::.i
k
;
u
k
/
M
1
and .i
1
;
u
1
/:::
2
2
\
.i
k
;
u
k
/
M
2
, implying .i
1
;
u
1
/:::.i
k
;
u
k
/
M
1
M
2
, from which follows
2
.M
1
\
M
2
/
#
U
.
t
u
1
:::
u
k
Search WWH ::
Custom Search