Hence our original assumption, that L is context free should be false.
Hence the lan guage L is not con text-free.
¨
Ì Exam ple 3.3.1: Check whether the language given by
L a b c m n m
m m n
=
≤ ≤
{
:
}
2
is a CFL or not.
Solu tion
Let s = a
n b
n c
2n , n being obtained from Pumping Lemma.
Then s = uvwxy, where 1 ≤
≤
| | .
vx n
Therefore, vx cannot have all the three symbols a, b, c.
If you assume that vx has only a’s and b’s then we can shoose i such that
uv
i
wx
i
y has more than 2n occurrence of a or b and exactly 2n occurences of c.
Hence uv wx y L
i
i
∉ , which is a contradiction. Hence L is not a CFL.
Ì Exam ple 3.3.2: “If L is regular and L ⊆ Σ
* , then Σ
*
− L is also a regular
set”—Prove this theorem.
Proof: Let L = T(M) where M
Q
q F
= ( , , , , )
Σ δ 0
is a Finite Automata.
We modify Σ, Q and δ as follows:
(a) If a ∈ −
Σ
Σ
1
, then the symbol ‘a’ will not appear in any string of
T(M).
Therefore we can delete ‘a’ from Σ 1 and all transitions defined by
‘a’.
Here T(M) is not affected.
(b) If Σ Σ
−
≠ ∅
1
, we can add a dead state d to Q. Let us define
δ( , )
,
d a d
= for all ‘a’ in Σ and δ( , )
,
q a d
= for all q in Q and a in
Σ Σ
− 1 .
Hence also T(M) is not affected.
Let us consider M obtained by applying (a) and (b) to Σ, Q and δ.
The new M is now written as ( , , , , )
Q
q F
Σ δ 0
. Let us define a new
automaton ‘M’ such that M
Q
Q F
′ = ( , , , , )
Σ δ
, where M ′ differs from M only in
its final states.
There w T M
∈
′
( ) iff δ( , )
q w Q F
0
∈ − and w T M
∉ ( ).
There fore, Σ
*
( )
− =
′
L T M is reg u lar.
¨
Ì Exam ple 3.3.3: Prove that the language L given by
L a b n
n
n n
=
≥
≠
{
|
,
}
0
1000
is context-free.
174
Theory of Automata, Formal Languages and Computation