1
$\begingroup$

This question already has an answer here:

I was searching for a difference on both ways of proving that a language is not regular but I didn't came up with much.

Let us take the following as an example:

$$ L = \{ a^n b^n \mid n \ge 0\} $$

Could someone tell me the differences between both theories and how to prove the language I brought is not regular according to each approach.

I know this is a basic example – that is the reason I chose it, make it simple rather than make it harder.

Thank you in advance!

New contributor
Isaac Michaan is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

marked as duplicate by Hendrik Jan, David Richerby, xskxzr, Evil, Yuval Filmus formal-languages Feb 11 at 18:21

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.

  • 5
    $\begingroup$ Start your quest here: How to prove that a language is not regular? $\endgroup$ – Hendrik Jan Feb 11 at 15:54
  • 1
    $\begingroup$ Our reference question, pointed out by Hendrik, explains how to use the methods. As for differences, isn't it self-evident from the descriptions of the two methods? I don't see any way in which having a list of the differences would help you with anything. A bicycle and a horse are two different ways of getting from A to B; does listing differences between the two help you understand either? $\endgroup$ – David Richerby Feb 11 at 16:06
0
$\begingroup$

The main difference between the pumping lemma and Myhill–Nerode theory is that the non-regularity criterion of Myhill–Nerode theory always holds for non-regular languages, whereas the same isn't true for the pumping lemma.

In other words, both the pumping lemma and Myhill–Nerode theory give you conditions which imply that a given language is not regular. If a language is not regular, then it is guaranteed that the Myhill–Nerode criterion will hold, but it is not guaranteed that the pumping lemma condition will hold. You can see an example in this question.

There are extensions of the pumping lemma which are guaranteed to work:

  1. Jaffe's pumping lemma: a language $L$ is regular iff all long enough words $w \in L$ can be decomposed as $w = xyz$, with $y \neq \epsilon$, such that for all $i \geq 0$ and all words $v$, $$xyzv \in L \text{ iff } xy^izv \in L.$$

  2. Block pumping lemma: a language $L$ is regular iff there exists a constant $k$ such that for all words $u,v,w_1,\ldots,w_k$ there are $1 \leq i < j \leq k$ such that for all $\ell \geq 0$, $$ uw_1\ldots w_k v \in L \text{ iff } u w_1 \ldots w_i (w_{i+1} \ldots w_j)^\ell w_{j+1} \ldots w_k v \in L. $$

In both cases, it in fact suffices to allow only $i = 0$.

(This material is from Handbook of Formal Languages, Volume 1: Word, Language, Grammar, Chapter 4 by Sheng Yu, Section 4.1.)

$\endgroup$

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