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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Patrick87 Sep 23 '14 at 14:29
  • $\begingroup$ @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? $\endgroup$ – Abhishek Bansal Sep 23 '14 at 14:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Patrick87 Sep 23 '14 at 15:59
  • 1
    $\begingroup$ Our reference question lists some possibilities. $\endgroup$ – Raphael Sep 23 '14 at 16:53
  • 1
    $\begingroup$ @user1990169 The converse is not true: even if $L$ is not regular, then $L\cup(A^*\setminus L)$ is regular. $\endgroup$ – Denis Sep 24 '14 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.

  • $\begingroup$ Thanks! Will try to relate this problem to other known problems and check. $\endgroup$ – Abhishek Bansal Sep 23 '14 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.

  • $\begingroup$ Pumping lemma, disguised (check the proof'). $\endgroup$ – vonbrand Feb 16 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.