Pumping lemma clarifications

91 Views Asked by At

http://www.cs.oberlin.edu/~asharp/cs383/handouts/pumping.pdf

I came across this and realized that what some people told me was completely wrong. We get to choose xyz, but the demon choose uvw and uvw = y.

How do we choose a good string for the pumping lemma?

Here, the guy said to me to pick a string and the demon get to choose uvw and uvw = s, to the whole string. He made a mistake, right?

1

There are 1 best solutions below

2
On

So one source tells you to consider strings $xuv^iwz$ and another tells you to consider $uv^iw$. How is $xu$ in the first different from $u$ in the second decomposition?