Information Technology Reference
In-Depth Information
Proof
Consider two arbitrary CFLs
L
(
H
1
)
and
L
(
H
2
)
generated by grammars
H
1
=
(
2
,
S
2
)
. Without loss of generality assume that their
non-terminal alphabets (and rules) are disjoint. (If not, prefix every non-terminal in the
second grammar with a symbol not used in the first. This does not change the language
generated.)
Since each string in
L
(
H
1
)
N
T
R
1
,
S
1
)
and
H
2
=(
N
T
R
1
,
1
,
2
,
2
,
L
(
H
2
)
consists of a string of
L
(
H
1
)
followed by a string
of
L
(
H
2
)
, it is generated by the context-free grammar
H
3
=(
·
N
3
,
T
3
,
R
3
,
S
3
)
in which
N
3
=
N
1
∪N
2
∪{
}
T
3
=
T
1
∪T
2
,and
R
3
=
R
1
∪R
2
∪{
→
}
,
. The new rule
S
3
S
3
S
1
S
2
→
S
1
S
2
generates a string of
L
(
H
1
)
followed by a string of
L
(
H
2
)
.Thus,
L
(
H
1
)
·
L
(
H
2
)
S
3
is context-free.
The union of languages
L
(
H
1
)
and
L
(
H
2
)
is generated by the context-free grammar
H
4
=(
N
4
,
T
4
,
R
4
,
S
4
)
in which
N
4
=
N
1
∪N
2
∪{
}
T
4
=
T
1
∪T
2
,and
R
4
=
R
1
∪
,
S
4
R
2
∪{
→
S
1
,
S
4
→
}
. To see this, observe that after applying
S
4
→
S
1
all subsequent
rules are drawn from
H
1
. (The sets of non-terminals are disjoint.) A similar statement
applies to the application of
S
4
→
S
4
S
2
S
2
.Since
H
4
is context-free,
L
(
H
4
)=
L
(
H
1
)
∪
L
(
H
2
)
is context-free.
The Kleene closure of
L
(
H
1
)
,namely
L
(
H
1
)
∗
, is generated by the context-free grammar
H
5
=(
N
1
,
T
1
,
R
5
,
S
1
)
in which
R
5
=
R
∪{
→
,
S
1
→
}
. To see this, observe
S
1
S
1
S
1
1
that
L
(
H
5
)
includes
,everystringin
L
(
H
1
)
,and,through
i
−
1 applications of
S
1
→
S
1
S
1
,
every string in
L
(
H
1
)
i
.Thus,
L
(
H
1
)
∗
is generated by
H
5
and is context-free.
We now use this result and Lemma
4.13.2
to show that the set of context-free languages
is not closed under complementation and intersection, operations defined in Section
4.6
.The
complement of a language
L
over an alphabet
Σ
, denoted
L
, is the set of strings in
Σ
∗
that are
not in
L
. The intersection of two languages
L
1
and
L
2
, denoted
L
1
∩
L
2
,isthesetofstrings
that are in both languages.
THEOREM
4.13.2
The set of context-free languages is not closed under complementation or inter-
section.
Proof
The intersection of two languages
L
1
and
L
2
can be defined in terms of the comple-
ment and union operations as follows:
L
2
=Σ
∗
−
(Σ
∗
−
(Σ
∗
−
L
1
∩
L
1
)
∪
L
2
)
Thus, since the union of two CFLs is a CFL, if the complement of a CFL is also a CFL, from
this identity, the intersection of two CFLs is also a CFL. We now show that the intersection
oftwoCFLsisnotalwaysaCFL.
The language
L
1
=
a
n
b
n
c
m
{
|
n
,
m
≥
}
is generated by the grammar
H
1
=(
N
1
,
T
1
,
0
R
1
,
S
1
)
,where
N
1
=
{
}
T
1
=
{
a
,
b
,
c
}
R
1
are:
S
,
A
,
B
,
, and the rules
a
)
→
d
)
B
→
B
c
S
AB
b
)
→
a
A
b
e
)
B
→
A
c
)
→
A
a
m
b
n
c
n
The language
L
2
=
{
|
n
,
m
≥
0
}
is generated by the grammar
H
2
=(
N
2
,
T
2
,
R
2
,
S
2
)
,where
N
2
=
{
S
,
A
,
B
}
,
T
2
=
{
a
,
b
,
c
}
and the rules
R
2
are:
Search WWH ::
Custom Search