Re: Pumping Lemma
 From: "surfivor" <surfver@xxxxxxxxx>
 Date: 23 Feb 2007 19:37:39 0800
On Feb 3, 9:40 pm, "meyousikmann" <meyousikm...@xxxxxxxxx> wrote:
I am having great difficulty understanding this concept. Please don't tell
me to search Google and read from the thousands of hits found as I have
already done that and can't seem to find the type of discussion that will
make the light go on. Perhaps I just will not ever understand this, but
considering it is part of my coursework, I really would like to.
Does anyone have a knack for describing this in the "Pumping Lemma for
Dummies" type of language. I can't stress enough how difficult this seems
for me so using other lemmas, corollaries, theorems, etc... is not going to
help. I am looking for the "dummies" type of discussion.
Here is a specific example that I am looking at:
L = {a^iba^jba^k  k = i + j}
and I don't even know where to start.
Any help?
This is a pumping lemma proof I had done. I forget alot of the
details, but I found it on my PC. I had tried to make as much sense of
it as I could in my own words I recall.
homework 3.6.2.a
Note: we'll use the following notation:
x**3 means: x to the power of 3
x{n} means: n copies of x
x <= y means: x is less than or equal to y.
x >= y means: x is greater than or equal to y.
let b = the maximum number of right hand side productions of
any rule in the context free grammar of G, coresponding to L(G).
let V = the number of nonterminals in G.
let k = b**((3V)+1)
let w = uv{2}xy{2}z such that w is derrived by the smallest
parse tree of height (3V)+1. Then w <= k because this
parse tree of height (3V)+1 can have at most k leaves.
note that for a tree of height (2V)+1, either one non terminal has 
V
occurences, or every non terminal could have 2 occurences, or some
could
have 2, some 3 and so on. Thus a height of (3V)+1 will guarantee
that at least one nonterminal has 3 occurences in the smallest parse
tree.
since the parse tree is 3V+1 in height, at least one
nonterminal must be repeated 3 times. Let R be one of these
nonterminals,
and let R1, R2 and R3 be a higher, middle, and lower instance of this
non terminal in the parse tree respecively as shown bellow:
R1
/  \
/  \
v  y
R2
/  \
/  \
v2  v2
R3

x
either v v2 > 0 or y y2 > 0, otherwise there is a smaller parse
tree, but we have allready said we have selected the smallest
parse tree. Additionally if v v2 = 0 and y y2 = 0, then
R2 and R3 can be collapsed into R1, because if any instances of R,
namely
R3 and R2 can each just produce x, than R1 can also just produce x.
If R2, and R3 are collapsed into R1, then we no longer have three
copies of R.
Given that we have shown there must be 3 copies of non terminal, there
must be some R that can not be collapsed, thus either v v2 > 0 or
y y2 > 0.
Given that R can reproduce itself, we can show that we can add
any number of instances of R by adding the same copy of v and y
strings.
The subtree for R would look like this:
R1
/  \
/  \
v  y
R2
/  \
/  \
v2  y2
R3
/  \
/  \
v3  y3
R4
/  \
/  \
v4  y4
R5
/  \
/  \
v5  y5
R6
/  \
/  \
v6  y6
.
.
.
Rn
/  \
/  \
vn  yn
Thus, any number of copies of v and y can be pumped into uv{n}xy{n}z
for n >= 0 and w will still be in the language L.
.
 References:
 Pumping Lemma
 From: meyousikmann
 Pumping Lemma
 Prev by Date: Re: Pumping Lemma
 Next by Date: On the General Construction for Kleene star in ContextFree Language
 Previous by thread: Re: Pumping Lemma
 Next by thread: List of accepted papers for CCC'07
 Index(es):