It should be understood that
(i) If S is sufficiently long string, then there are two substrings, v and
x, somewhere in S. There is stuff (u) before v, stuff (w) between v
and x, and stuff (y), after x.
(ii) The stuff between v and x won’t be too long, because | vwx | can’t
be larger than m.
(iii) Substrings v and x won’t both be empty, though either one could
be.
(iv) If we duplicate substring v, some number (i) of times, and
duplicate x the same number of times, the resultant string will also
be in L.
3.3.2 Def i ni tions
A variable is useful if it occurs in the derivation of some string. This requires
that
(a) the variable occurs in some sentential form (you can get to the
variable if you start from S), and
(b) a string of terminals can be derived from the sentential form (the
variable is not a “dead end”).
A variable is “recursive” if it can generate a string containing itself. For
example, variable A is recursive if
S uAy
⇒
*
for some values of u and y.
A recursive variable A can be either
(i) “Directly Recursive”, i.e., there is a production
A x Ax
→ 1 2
for some strings x x
T V
1
2
,
(
) ,
*
∈ ∪
or
(ii) “Indirectly Recursive”, i.e., there are variables x i and productions
A
X
X
X
X
X
X
A
N
→
→
→
→
1
1
2
2
3
K
K
K
K
K
K K
3.3.3 Proof of Pumping Lemma
(a) Suppose we have a CFL given by L. Then there is some context-free
Grammar G that generates L. Suppose
Pushdown Automata
171