Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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!
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:
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.$$
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.)
