# pumping lemma - choice of partition

there is some thing in pumping lemma that I don't understand it.
I think about application to prove irregularity of language.
We have for each word (actual length) find partition: $xyz$ such that $\forall i \ge 0 xy^iz \in L$.
So we can find word, but tell me - if we can choose partition ? (so choose $y$) ? Maybe we should check each possible partition ?

Recall that all regular langauges satisfy the pumping lemma, which we capture by the following informal proposition: $$\text{regular}\implies\text{pumping lemma}.$$ Applying modus tollens (a.k.a. contrapositive), we get $$\neg\text{pumping lemma}\implies\neg\text{regular}.$$ Therefore, to prove a language is not regular, it suffices to show that it does not satisfy the pumping lemma. For any regular language $L$, the pumping lemma states the following: $$\exists p\geq1(\forall w(\left|w\right|\geq p\Rightarrow\exists x,y,z(w=xyz\wedge\left|y\right|\geq1\wedge\left|xy\right|\leq p\wedge\forall i\geq0(xy^{i}z\in L))))$$ Taking the negation of this statement, $$\forall p\geq1(\exists w(\left|w\right|\geq p\wedge\forall x,y,z(w=xyz\Rightarrow(y=\epsilon\vee\left|xy\right|>p\vee\exists i\geq0(xy^{i}z\notin L)))))$$ As you can see, we have to show that for all pumping lengths $p$, there exists a word $w$ at least as long as the pumping length $p$ such that for all partitions $w=xyz$, at least one of the following is true: (i) $y$ is the empty string (i.e. $w=xz$), (ii) $|xy|$ is greater than the pumping length, or (iii) there exists an $i$ such that the pumped string $xy^{i}z$ is not in $L$.
Let $L=\{a^{n}b^{n}\colon n\geq0\}$ be a language, which we will prove to be not regular. Suppose $L$ satisfies the pumping lemma. Let $p$ be an arbitrary pumping length. Let $w=a^{p}b^{p}$, and note that $|w|\geq p$. Let $w=xyz$ be an arbitrary partition of $w$. Suppose $y$ is not empty and $|xy|\leq p$. Since $|xy|\leq p$ and $w=a^{p}b^{p}$, $y=a^{k}$ for some $1\leq k\leq p$. We can now "pump" to conclude that $w^\prime=xy^{2}z$ is a word in the language $L$. This is, however, a contradiction, since $w^\prime$ has more $a$ characters than $b$ characters.
• Fix a partition $w=xyz$. If any one of (i) and (ii) are true, then $y=\epsilon\vee\left|xy\right|>p\vee\exists i\geq0(xy^{i}z\notin L)$ is true. Therefore, suppose neither (i) nor (ii) are true, we need to show (iii) to show that the statement is true. – parsiad Jun 27 '16 at 14:35