Proving that a Language is non-Regular Prove that $L_2 = \{ w \in \{a,b\}^* \mid w = a^ib^j, i \neq j \}$ is not regular.


I was wondering if my intuition holds for proving this language as not regular:

Let $q = \max(i, j) - \min(i, j)$.

Case 1: $i &gt; j$

Let $$L_3 = b^q \Rightarrow L_2 \cdot L_3 = \left \{ a^ib^{j+q} \right \}=\left \{ a^ib^i \mid i \ge 0 \right \}.$$

And then do the same for when $j &gt; i$.

Is this allowed?
No that's not allowed, since $i$ and $j$ are not fixed.

Here is a solution using pumping lemma:


  The better approach is to apply pumping lemma. 
Let $x = a^{n!}b^{(n+1)!}$, where $n$ is the pumping constant. Note that $u = a^i$ and $v=a^j$ for some $i\geq 0$ and $j&gt;0$ plus $i+j\leq n$.

Then we let $k = 1+\frac{n\cdot n!}{j}$. After that, $uv^kw = a^mb^{(n+1)!}$ where $m = n!+(k-1)j = n!+n\cdot n! = (n+1)!$. Contradiction.


Here is another solution using closure result (which is less tricky):


  Suppose $L_2$ is regular. Then $(\Sigma^* - L)\cap a^*b^* = \{w\in\{a, b\}^*|w=a^ib^j, i=j\}$ is regular by closure result. Then it's easy to gain a contradiction by applying pumping lemma to $(\Sigma^* - L)\cap a^*b^*$.