pumping lemma - choice of partition

Question

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 ?

Answer 1

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$.

If any one of (i) or (ii) is true for a partition, we need not consider it in our proof by contradiction. Therefore, we can look only at partitions for which (i) and (ii) are false, and try to show that (iii) is true. The example on Wikipedia is quite helpful in demonstrating this. It is paraphrased below:

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.