Irregularity of $\{a^iba^j : i \neq j\}$ using pumping lemma

Question

Proving the language $L=\{ a^i b a^j |\ i<j,\text{ or }i>j;\ i,j>0 \} $ is not regular, I am trying to use the pumping lemma for regular languages:

pumping length $:= m$

case 1: $i<j; j=m$

$w_1 = a^i b a^m = xyz$
$|xy| < m$
$|y| > 0$

$\Rightarrow$
$y$ can be:

• $a$s only
• $a$s + $b$
• just $b$
  

However, this leads to $xy^hz\ \not \in L\ \forall h,\ h>0$.

case 2: $i>j; i=m$

$w_2 = a^m b a^j = xyz$
$|xy| < m$
$|y| > 0$

$\Rightarrow$
$y$ can be:

• $a$s only

Pumping with this $y$:
$xy^hz\ \in L\ \forall h$ holds true.

As this answer does not seem to even consider the second case, is the first case sufficient to proof the language is not regular?
However, taking a look at this answer I think I'd have to considere the second case as well, in order to cover all possible $xyz$ combinations.

Answer 1

Here is the contrapositive form of the pumping lemma, which is what we use to prove that a language is not regular:

Let $L$ be a language. Suppose that for all $p \geq 1$ there exists a word $w \in L$ of length at least $p$ such that for every decomposition $w=xyz$ in which $|xy| \leq p$ and $y \neq \epsilon$ there exists an integer $i \geq 0$ such that $xy^iz \notin L$. Then $L$ is not regular.

Using the pumping lemma directly for the language $L$ in the question is a bit tricky. Given $p \geq 1$, let $w = a^p b a^{p+p!} \in L$; note that $|w| \geq p$. We have to show that for every decomposition $w = xyz$ in which $|xy| \leq p$ and $y \neq \epsilon$ there exists an integer $i \geq 0$ such that $xy^iz \notin L$. Consider any such decomposition. It is easy to check that $y = a^\ell$ for some $1 \leq \ell \leq p$, and that $xy^ij = a^{p+(i-1)\ell}ba^{p+p!}$. For $i = p!/\ell+1$ (which is an integer!), $xy^ij = a^{p+p!}ba^{p+p!} \notin L$. Thus the condition in the pumping lemma is satisfied, and we conclude that $L$ is not regular.

Answer 2

Let $$L_1 = \{a^iba^j | i\lt j\text{ and } i,j\gt 0\}$$ $$L_2 = \{a^iba^j | i\gt j\text{ and } i,j\gt 0\}$$

Here, $$L = L_1\cup L_2$$

From Case 1, you have shown that $L_1$ is not regular.

You are trying to conclude that if $L_1$ is not regular, $L$ is not regular. It is not sufficient that $L_1$ is not regular to show that $L$ is not regular. A simple counter example will be $L_1 = \{a^nb^n|n\gt 0\}$ and $L_2=\{a^m b^n |m\ne n\}$. Neither $L_1$ nor $L_2$ are regular, yet their union is regular.

---

In the first answer you have linked, it is not true that only one case has been considered. You need to find any one string $s$ whose length is at least than every possible pumping length $p$ such that no matter how you partition it into $s=xyz$, the resulting string goes out of the language.

The key difference between your case 1 and the answer you linked is that you have taken a string in $L_1\subset L$, pumped it and shown that it goes out of $L_1$ only. However, what you need to show is that it cannot lie in $L$ at all, no matter how you split it and pump it, which is what the linked answer shows.