# Prove that the language $\{a^ib^i | i\geq 0\}$ is not regular? (Do we just consider $a^nb^n$, where $n$ is the pumping length?

I think to prove that $$\{a^ib^i | i\geq 0\}$$ is not regular, we just have to consider the string $$a^nb^n$$ (which is in the language) and apply the pumping lemma. But I'm not sure how to proceed using the pumping lemma (even though I know it applies with our choice of string, since the string is at least $$n$$ long).

To apply the pumping lemma for regular languages:

1. You assume some pumping length $$p > 0$$: Suppose a pumping length $$p$$.
2. You pick a string $$s$$ such that $$|s| \geq n$$: Indeed, $$a^pb^p$$ is a good one since $$|a^pb^p| = 2p \geq p$$.
3. Now, you have to consider all the partitions of $$s$$ as $$xyz$$, such that
1. $$|y|>0$$ and
2. $$|xy| \leq p$$.

In this case, the 2nd inequality restricts $$y$$ to contain only $$a$$'s. Therefore, all the possible partitions are of the form $$y = a^k$$, $$x = a^{p-k-r}$$ and $$z = a^rb^p$$ for $$k$$ and $$r$$ such that $$k > 0$$ and $$p \geq k + r$$.

1. For every possible partition of the previous step, you have to show that there is some $$i\in\mathbb{N}$$ such that $$xy^iz$$ is not in the language.

Here, consider $$i = 0$$. Then $$xy^0z = xz = a^{p-k-r}a^rb^p = a^{p-k}b^p$$. It is now a matter of showing that $$p-k\neq p$$, or, equivalently, that $$k > 0$$ which is already true.

• Apologies for the late response, I just wanted to say thank you! Your response helped my understanding a lot! – James Ronald Mar 2 '20 at 15:11

In this particular case, you can use the pumping lemma with any word of length at least $$p$$ (the pumping length). Indeed, consider any word $$w = a^nb^n$$, and suppose that we are given some decomposition $$w = xyz$$ where $$y$$ is non-empty and $$xy^tz \in \{ a^ib^i \mid i \geq 0 \}$$ for all $$t$$ (we don't even need the bound on $$|xy|$$). If $$y$$ consists only of $$a$$'s, then $$xy^2z$$ will have more $$a$$'s than $$b$$'s; if it consists only of $$b$$'s, then $$xy^2z$$ will have more $$b$$'s than $$a$$'s; and if it consists of both, then $$xy^2z \notin a^*b^*$$.

If instead of your language we consider the language of all words with equally many $$a$$'s and $$b$$'s (but not necessarily in the format $$a^*b^*$$) then the above argument would fail, and you would have tobe more careful when choosing your word; however, $$a^pb^p$$ would still work.