Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$ is not regular by use of Pumping Lemma

Question

I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it.

Question

Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$ is not regular by use of Pumping Lemma. I know the correct way of prove with factorial or using closure. However today someone explain a way to me and I couldn't find what is wrong with it. I think it is wrong but if it is true, is it possible to explain why?

Proof (Maybe correct):

we suppose that that $L$ is regular and there is a machine with $u$ state that accept it. If it is a NFA, we can convert any NFA to DFA with for example $k$ state.
We have a group of strings like $a^kb^{k + t}$ for every $1 \le t \le k$ which accepted with machine.
There is only one way for read $a^k$ because our machine is DFA so we can write $a^k = a^sa^ta^p$ that $|a^sa^t| \le k$ and $|a^t| \ge 1$ and $a^t$ is cycle, so with pumping lemma we can say that $a^{k + t}b^{k + t}$ (with one more time of cycle) belongs to $L$ and it is contradiction. (one of our strings in our first group will fail) so our language is not regular.

---

My Problem

Because we we get a group of strings (instead just one strings which is normal in proves) and use same $t$ when break $a^k$ to $a^sa^ta^p$, is it true anymore? If no or yes, please explain.

My explanation

I think we can construct a NFA that accept each of $a^kb^{k + t}$ (for each $t$) with different size of cycle (cycle that is used in pumping lemma) however when convert it to a DFA, I can't understand how to prove it.

Answer 1

This is a trick question. Your proof doesn't quite work, but can be turned into a proof, as follows.

Let $p$ be the constant in the pumping lemma, and consider the word $a^pb^{p+p!} \in L$. According to the pumping lemma, it can be decomposes as $xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. Since $|xy| \leq p$, we must have $y = a^q$ for some $q \leq p$; since $y \neq \epsilon$, we must have $q \geq 1$. Let $i = p!/q + 1$. Then you can check that $xy^iz = a^{p+p!} b^{p+p!} \notin L$, contradicting the pumping lemma.

Here are two more proofs. The first uses closure properties. If $L$ were regular then so would the following language be: $a^*b^* \setminus L = \{ a^nb^m : n = m \}$. However, this language is known to be non-regular.

Another proof uses Myhill–Nerode theory. Let us say that two words $x,y$ are incomparable if there exists a word $z$ such that $xz \in L$ but $yz \notin L$, or vice versa. In any DFA for $L$, we must have $\delta(q_0,x) \neq \delta(q_0,y)$ (why?). Therefore, if we can find an infinite collection of pairwise incomparable words, then the language is not regular (why?). In the case of $L$, such a collection consists of the words $a^i$ for all $i \geq 0$. Indeed, if $i \neq j$ then $a^ib^j \in L$ whereas $a^jb^j \notin L$, showing that $a^i,a^j$ are incomparable.