# Prove that the language is not regular without using Pumping Lemma

I am practising problems on Regular Languages and I came across this question:

Prove that the language $$\{a^m b^n : m ≥ 0, n ≥ 0, m \ne n\}$$ is not regular. (Using the pumping lemma for this one is a bit tricky. You can avoid using the pumping lemma by combining results about the closure under regular operations.)

I have tried to prove it using pumping lemma in the following way:
Let p be a sufficiently large integer, then we construct the string: $$s = a^pb^{p + p!}$$ Now by pumping lemma conditions, the string $s$ can be written as $xyz$ where $|xy| \le p$. Hence $xy$ contains only $a$'s.
If we choose any substring $y$ of length $k \le p$ from $xy$, we can always find a $C$ such that $$p+C*k = p + p!$$

We can also prove it if we choose $s$ to be just the single character string $a$ and then we pump down.

Q1. Please let me know if there is a flaw in the above proofs.
Q2. How can closure properties be applied to prove the above? Till now I have applied closure properties to prove regularity, but never the converse.

• Q1) Looks sound. Q2) You know $a^nb^n$ is non-regular, presumably. What's the complement of this? What's the intersection with the regular language $a^*b^*$? FYI: the Myhill-Nerode theorem also gives a proof technique you could use. Better still, you can use it to prove a language regular, which the PL cannot do. – Patrick87 Sep 23 '14 at 14:29
• @Patrick87 Thank you! I will certainly look into Myhill-Nerode theorem. Regarding closure properties I know that if two languages are regular, then their intersection and complement are also regular. But is the converse also true, ie., is the intersection of a non-regular language with a regular/non-regular language always non-regular? – Abhishek Bansal Sep 23 '14 at 14:36
• The proof involving closure properties might look like: assume $L$ is regular; then $L^C \cap a^*b^*$ must be regular by closure properties. But this is $a^nb^n$, a canonical non-regular language. Proof by contradiction follows. – Patrick87 Sep 23 '14 at 15:59
• – Raphael Sep 23 '14 at 16:53
• @user1990169 The converse is not true: even if $L$ is not regular, then $L\cup(A^*\setminus L)$ is regular. – Denis Sep 24 '14 at 7:12