Draw a Venn diagram illustrating the containment relations between the four classes of languages such as regular, deterministic context-free, context-free, and complements of context-free. Supply a language for each nonempty region in your diagram.
Prove the following stronger versions of the Pumping Lemma for CFLs and then say in what sense they are stronger:
(a) Let
L
be a CFL over an alphabetΣ
containing at least one nonempty string. There is
n
≥ 1 such that if
w
∈
L
is of length at least
n, then
w
can be rewritten as
w
=
uvx yz
such that
v
_
ε, y
_
ε,
(vx y) ≤
n,
and for each
k
∈ N, uvkxykz
∈
L.
(b)
Ogden’s Lemma: Let
L
be a CFL over an alphabet
Σ.
Let
L
contain at least one nonempty string. Then there exists an
n
≥ 1 such that the following is satisfied: Let
w
∈
L
with (w)
> n.
Mark any
n
or more occurrences of symbols in
w
arbitrarily. Then there exists strings
u, v, x, y, z
∈
Σ
∗ such that
1.
w
can be rewritten as
w
=
uvx yz,
2. the string
vwx
contains
n
or fewer marked symbols,
3. each of the strings
uz, vy, x
contains at least one marked symbol, and
4. for all
k
∈ N, the string
uvkxykz
∈
L.