7
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 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
    Commented Sep 23, 2014 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
    Commented Sep 23, 2014 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
    Commented Sep 23, 2014 at 15:59
  • 1
    $\begingroup$ Our reference question lists some possibilities. $\endgroup$
    – Raphael
    Commented Sep 23, 2014 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
    Commented Sep 24, 2014 at 7:12

3 Answers 3

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! Will try to relate this problem to other known problems and check. $\endgroup$
    – Abhishek Bansal
    Commented Sep 23, 2014 at 15:34
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Pumping lemma, disguised (check the proof'). $\endgroup$
    – vonbrand
    Commented Feb 16, 2020 at 5:16
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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