Pumping lemma $L=\{a^ib^j | i \neq j ; i,j \ge 0\}$

Question

So, let's have language $L=\{a^ib^j | i \neq j ; i,j \ge 0\}$ I have to prove that it's not regular. \begin{align} \omega=a^nb^{n+1}=a^{n-1}ab^{n+1} \end{align}

\begin{align} x&=a^k\\ y&=a\\ z&=a^{n-k-1}b^{n+1}\\ \\ i=2:xy^iz&=a^ka^ia^{n-k-1}b^{n+1}\\ &=a^ka^2a^{n-k-1}b^{n+1}\\ &=a^{n+1}b^{n+1}\\ \end{align}

$\#_a(\omega)=\#_b(\omega)\implies a^{n+1}b^{n+1} \not\in L $

I'd like to ask if this is a correct proof?

Answer 1

The problem with your approach is that you are determining the substring $y$ that you intend to pump. Recall the statement of the Pumping Lemma:

If $L$ is regular, then there is an integer $p \geq 1$ such that for every string $w$ in $L$ of length $\geq p$ you can decompose $w$ into $xyz$ such that etc.....

To show that a language $L$ is not regular you must show that no such integer $p$ exists. That is, for every $p \geq 1$ you must exhibit (at least) one string $w$ in $L$ of length $\geq p$ such that there is no decomposition of $w$ into $xyz$ such that etc.....

You have essentially only provided a single decomposition of your $w = \mathtt{a}^{n} \mathtt{b}^{n+1}$ which doesn't allow you to pump and remain in your language. However, there might be other decompositions that do work. For example, if you take $y = \mathtt{a}^2$ (so that $x = \mathtt{a}^{k}$ and $z = \mathtt{a}^{n-k-2} \mathtt{b}^{n+1}$), you will find that this can be pumped. (The number of $\mathtt{a}$s in $xy^iz$ will always be of opposite parity to the number of $\mathtt{b}$s.)