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

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.

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.

• Thanks for answer. as I mentioned, I know the correct way of prove (the method 1 and method 2 which you said) and method 3 is very beautiful. however I want to know what is wrong about that answer in question or if it is true, prove it. Is it possible to help me? – Amin Oct 29 '18 at 3:54
• Well, your proof doesn't work. It doesn't "compile", i.e., doesn't constitute a formal argument. One correct way to implement the same idea is method 1. – Yuval Filmus Oct 29 '18 at 3:57
• I know that is not correct but I can give a strong statement which state that is not correct for my friend. can you explain exactly which part of proof is not correct and why? – Amin Oct 29 '18 at 4:30
• The part starting “there is only one way”. – Yuval Filmus Oct 29 '18 at 6:21
• why? because it is DFA and it is only one way? can you explain more. – Amin Oct 29 '18 at 6:50