Using pumping lemma to prove {a^ib^j | i > j} non-regular

Question

I'm having issues using the pumping lemma to prove $L_2 = \{a^ib^j \mid i > j \}$ is non-regular. It's obvious to know that the language is non-regular as there is no way of tracking $a^{i's}$ and $b^{j's}$

So I've done some digging. On page 2 here I found a proof. However, it doesn't make sense to me.

Here is the proof, I will list my understandings as we go through the proof:

Assume by way of contradiction that $L_2\in \mathrm{REG}$, then $L_2$ satisfies the conditions of the pumping lemma. Let $p > 0$ be the pumping constant. Consider the word $w = a^{p+1}b^p$.

Makes complete sense.

Clearly $w \in L_2$ and $|w| > p$, so according to the pumping lemma there exist $x, y, z ∈ Σ^∗$ such that $w = xyz,$ $ |xy| ≤ p,$ $ |y| > 0$ and for all $i ≥ 0$ it holds that $xy^iz ∈ L$.

Now if an $i$ is chosen to be $0$, this would conflict with $|y| > 0$? It seems it's using $L$ instead of $L2$. Is there a reasoning?

Since $|xy| ≤ p$, then $x = a^n, y = a^m$, and $z = a^kb^{p+1}$ such that $m + n + k = p$, and $m > 0$.

This makes sense to me, as $z$ is equal to the rest of the $a's$ not in $x$ and $y$ plus all the $b's$.

We pump with $i = 0$ and get the word $xz = a^nz = a^na^kb^{p+1}$. Since $m+n+k = p+1$ and $m > 0$, then $n+k < p+ 1$.

Now this doesn't make sense to me. Pumping down ridding of $y$ contradicts the $|y| > 0$ rule and how does $m+n+k$ change to now equal $p+1$

Thus, $xz \notin L_1$, in contradiction to the pumping lemma. So $L_2$ is not regular. Note that it is crucial to “pump down” for this language.

If you guys can help me understand this proof, that would be great thanks

Answer 1

Now if an $i$ is chosen to be 0, this would conflict with $|y|>0$?

Note it's $|y|>0$, not $|y^i|>0$, so there's no problem.

All your other confusions come from the typos in the proof. I rewrite the proof (the fixed typos are colored red) as follows.

... Clearly $w \in L_2$ and $|w| > p$, so according to the pumping lemma there exist $x, y, z \in \Sigma^∗$ such that $w = xyz,$ $ |xy| \le p,$ $ |y| > 0$ and for all $i \ge 0$ it holds that $xy^iz \in L$. Since $|xy| \le p$, then $x = a^n, y = a^m$, and $z = a^kb^\color{red}p$ such that $m + n + k = \color{red}{p+1}$, and $m > 0$. We pump with $i = 0$ and get the word $xz = a^nz = a^na^kb^\color{red}p$. Since $m+n+k = p+1$ and $m >0$, then $n+k \color{red}{\le p}$ ...