1
$\begingroup$

This question already has an answer here:

I know that the language $\{a^m b^n | n\neq m\}$ satisfies the pumping lemma, but it's still not regular (I have to count the # of a's and b's). How can I formally prove it?

$\endgroup$

marked as duplicate by Raphael Jan 24 '14 at 17:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ You can use the Myhill-Nerode theorem. $\endgroup$ – FrankW Jan 24 '14 at 14:39
  • 1
    $\begingroup$ This question has been asked before on this site. $\endgroup$ – Yuval Filmus Jan 24 '14 at 16:03
1
$\begingroup$

Suppose $L = \{ a^m b^n : m \neq n \}$ were regular. Then $a^*b^* \setminus L = \{ a^n b^n \}$ would also be regular.

There is a variant of the pumping lemma in which you mark certain symbols of your choice (at least as many as the pumping constant $p$), and then the pumped part is certain to contain at least one of these symbols (and at most $p$). Now consider $a^p b^{p+p!}$ for large enough $p$, and mark the $a$ part. We arranged things so that whatever the length of the pumped part (which must consist solely of $a$s), you can pump it to exactly $a^{p+p!} b^{p+p!}$.

Another possibility is to use the Myhill--Nerode theorem. The words $a^n$ ($n \in \mathbb{N}$) are an infinite set of pairwise inequivalent words: if $n \neq m$ then $a^n b^n \notin L$ yet $a^m b^n \in L$.

Take your pick...

$\endgroup$
  • $\begingroup$ I would not consider that a variant of the Pumping Lemma. For regular languages one should be able to pump within the first whatever symbols. Wikipedia agrees. $\endgroup$ – Hendrik Jan Jan 24 '14 at 16:48

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