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.
1) your proof is correct (and nice).

2)They could mean prove that the complement is not regular (this is a classic result, and the proof is simpler). More generally, if you saw in course some languages that are not regular, you can probably reduce one of them to this one by closure operations.

Another technique without pumping lemma is to show that the number of Myhill-Nerode equivalence classes is infinite.