# Using pumping lemma to prove that $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \}$ is irregular

Given the following language:

$$L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \}$$

I am trying to prove that it is not regular. On the one hand my intuition tells me that the language is non-regular as there is no way of tracking $$a^{i's}$$ and $$b^{j's}$$.

However, when I try to prove that it is irregular using the pumping lemma I have trouble finding which word I should use to arrive at a contradiction.

Any suggestions?

• You can take the word $a^pb^p$, where $p$ is the constant promised by the pumping lemma. May 2 at 18:08
• @YuvalFilmus Thanks! I just proved it with your word :) May 2 at 19:07

You can use the word $$a^pb^p$$, where $$p$$ is the constant promised by the pumping lemma.