Proof using Pumping Lemma

86 Views Asked by At

For the example proof below, how could $|v|\ge1$ when we've already set it to $v^0$ (pump $0$ times)?

enter image description here

Reference:

enter image description here

1

There are 1 best solutions below

0
On

There is no inconsistency, since $v$ and $v^i$ are different objects. The first condition in the pumping lemma of the decomposition states that $v$ is non-empty, i.e. $|v| \geq 1$. However, when "pumping down", i.e. setting $i = 0$, then we obtain $v^0 = \lambda$ no matter the length of the original $v$.

So the first condition of the decomposition states that $v$ is non-empty, and the second one states that if we either remove $v$ or repeat it an arbitrary number of times in the decomposition, then the resulting string is still in our language.