# 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. Sep 23, 2014 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? Sep 23, 2014 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. Sep 23, 2014 at 15:59
• – Raphael
Sep 23, 2014 at 16:53
• @user1990169 The converse is not true: even if $L$ is not regular, then $L\cup(A^*\setminus L)$ is regular. Sep 24, 2014 at 7:12

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.

• Thanks! Will try to relate this problem to other known problems and check. Sep 23, 2014 at 15:34

Assume a finite state machine. Since the state machine is finite there are n != m where $$a^n$$ and $$a^m$$ end up in the same state. So $$a^nb^n$$ and $$a^m b^n$$ both end up in the same state, so are either both in L or both not in L, which contradicts the definition of L.

• Pumping lemma, disguised (check the proof'). Feb 16, 2020 at 5:16

To use closure properties, suppose $$L$$ is regular. Then it's complement, $$\overline{L}$$ is also regular, and so is $$\overline{L} \cap \mathcal{L}(a^* b^*) = \{ a^n b^n \colon n \ge 0\}$$, but that one is known non-regular. Contradiction.