Proof: Let us assume that
L
a b
A = {
}.
1000 1000
Then, since L 1 is finite, it is regular.
It is obvious that
L a b n
L
n n
=
≥ ∩
{
|
}
.
0
1
According to the theorem: “If L 1 is a CFL and L 2 is a regular language,
L
L
1
2
∩ is context-free”, we have the following.
By closure of regular languages under complementation and closure of
context free languages under regular intersection, the language L given by
L a b n
n
n n
=
≥
≠
{
|
,
}
0
1000
is con text-free.
¨
Ì Exam ple 3.3.4: Check whether the language given by
L w a b c
n w n w n w
a
b
c
= ∈
=
=
{
{ , , } | ( )
( )
( )}
*
is not context-free.
Proof: If L is assumed to be context-free, then
L L a b c
a b c n
n n n
∩
=
≥
(
) {
|
}.
* * *
0
which is also context-free.
But it is a fact that the latter is not context-free.
Therefore we conclude that
L w a b c n w n w n w
a
b
c
= ∈
=
=
{
{ , , } | ( )
( )
( )}
*
is not con text-free.
¨
Ì Exam ple 3.3.5: Determine whether the language given by
L a n
n
=
≥
{ |
}
2
1 is context-free or not.
Solu tion
Let us assume that
s a
n
=
2
.
s = uvwxy, where 1 ≤
≤
| | .
vx n which is true
since,
|
|
(
vwx n
≤
by Pumping Lemma)
Pushdown Automata
175