Using Pumping Lemma prove that the language $L = \{a^ib^j \mid i,j \in N \}$ is Not Regular.

Question

Using Pumping Lemma prove that the language $L = \{a^ib^j \mid i,j \in N \}$ is Not Regular.

Proof:

Assume that $L$ is Regular. Pumping Length = $P$. We choose $w = a^{P-2}b^{P+2} \in L$

We divide $w$ in $xyz$. $x= a, y = a^{P-3}bb, z = b^P$

Now we Pump with $i = 2$. $xy^iz = xy^2z$ = $aa^{P-3}bba^{P-3}bbb^P$ = $a^{P-2}bba^{P-3}b^{P+2} \notin L$. QED

Did I do it right?

Answer 1

Your language is regular and equal to $a^*b^*$. That being said, your application of the pumping lemma is faulty.

Assume that $L$ is Regular. Pumping Length = $p$. We choose $w = a^{p-2}b^{p+2} \in L$.

Apart from the telegraphic style, so far, so good.

We divide $w$ in $xyz$. $x= a, y = a^{p-3}bb, z = b^p$.

Wrong! The pumping lemma just tells you there must be some decomposition $w=xyz$ with $|xy| \leqslant p$ and $|y| \geqslant 1$ such that $xy^iz \in L$ for every $i \geqslant 0$. The decomposition you propose may not work, but there might be another decomposition that works. And indeed, the decomposition $x = a^{p-3}bb$, $y = b^p$ and $z=1$ will work since $a^{p-3}bb(b^p)^n \in L$ for all $n$. So you didn't find a contradiction.

Answer 2

Let's suppose that $w$ is regular.

We can take the string $s = a^ib^i$. Like s $\in w$ and $|s| \ge p$, the pumping lemma states that we can separate $s$ in 3 parts that are: $xyz$. With $n \gt 0, xy^iz \in w$. Because one of the lemma condition says that $|xy| \le p$, $y$ must consist only of $0s$ otherwise $|xy| \ge p$.

If we take the string $xyyz$ (which is supposed to be regular), we notice that we have more $0s$ than $1s$. So it's a contradiction.