I have a problem that a friend helped solve but I did not entirely follow the explanation. I would hope someone could break it down for me. I understand the gist of the PL, but I do not understand how the rules apply here and contradict the language. I hope you can help me better understand this problem for any future problems I have by explaining the train of thought!
Let $A=\{1^ky\ |\ y\in\{0,1\}^*{\rm\ and\ }y{\rm\ contains\ at\ most\ }k{\rm\ 1s,\ for\ any\ }k\ge1\}$. Prove by the pumping lemma that $A$ is not regular.
Assume $A$ is a regular language. Then the pumping lemma applies and let $p$ be the constant. Select $s=1^p0^p1^p \in A$ with $|s| = 3p > p$. Also, $s = xyz$ such that $|y| > 0$ and $|xy| \leq p$. Fix $i \geq 1$, then $y = 1^i$. So $xz=1^{p-i}0^p1^p \notin A$.
Why is this a contradiction???
The pumping lemma says that if $A$ were regular, there would be some decomposition $s=xyz$ such that $|y|>0$, $|xy|\le p$, and $xy^iz\in A$ for all $i\ge 0$. Since $|xy|\le p$, and $s=1^p0^p1^p$, the substring $xy$ must be entirely contained within the initial $1^p$ substring of $s$. Thus, $x=1^r$ and $y=1^t$ for some integers $r$ and $t$ such that $r\ge 0$, $t\ge 1$ (since $t=|y|>0$), and $r+t\le p$. Then
$$s=\color{blue}x\color{crimson}yz=\color{blue}{1^r}\color{crimson}{1^t}1^{p-r-t}0^p1^p\;.$$
Now $xy^iz$ is supposed to be in $A$ for any $i\ge 0$, so in particular $xy^0z=xz$ should be in $A$. But
$$\color{blue}xz=\color{blue}{1^r}1^{p-r-t}0^p1^p=1^{p-t}0^p1^p\;,$$
and $t\ge 1$, so $p-t<p$. This word begins with $p-t$ ones followed by a zero, so if we try to match it up with the form $1^ky$ in the definition of $A$, the largest value of $k$ that it can match is $k=p-t$, which is less than $p$. But then $y$ has to be $0^p1^p$, which has more than $k$ ones, and $xz$ can’t be in $A$ after all.