# Showing that the pumping lemma cannot prove that some language is not regular

I have this language $L = a^* \cup \left \{ a^mb^n|m>n\geq 0 \right \}^*$ I have to prove that this language is not regular but still satisfies the pumping lemma for regular languages (Since the pumping lemma is a necessary but not sufficient condition for a language to be regular). First I made the leap that $L$ is equivalent to $L' = \left \{ a^mb^n|m>n\geq 0 \right \}^*$ since this language already contains $a^*$(I hope it's correct). My question is: to prove that the pumping lemma holds is sufficient to prove that exists a word in this language that satisfies the lemma or that must hold for all words in the language? For example in this case we could consider the word $aaa$ it's easy to say how this word satisfies the pumping lemma because $aa^ia \in L' \space \forall i \geq 0$.
This means that proving the pumping lemma holds for a language is easy (must find an instance in whitch it holds) but proving it doesn't hold is harder (must prove that it doesn't hold for all instances of the language).

• For a language $L$ to "satisfy" the pumping lemma (for regular languages) there must be an integer $p$ such that every word $w\in L$ with length $|w|\ge p$ can be factored as $w=xyz$ with $|y|>0$, $|xy|\le p$, and $xy^iz\in L$ for all $n=0,1,2,\dotsc$. – Rick Decker Jul 16 '15 at 14:33
• Please fix your title. It does not ask the question I think you want to ask. – reinierpost Jul 16 '15 at 15:59
• A single instance won't do: What you need to find is a lower bound $p$ and a way of obtaining for any $w\in L$ with $|w|\ge p$ a decomposition as required by the pumping lemma. Hint: $p=1$ should work. – Klaus Draeger Jul 16 '15 at 17:44
• @Klaus Draeger: well there is the kleene star over the language $L'$ . ATreinierpost how should I change the title? My main issue was about satisfying the pumping lemma and I thought wrongly it could be done that way. I'm open to suggestions anyways – Crysis85 Jul 16 '15 at 17:46
• Yes, spotted that too late, sorry. I thought I had removed that comment quickly enough :) – Klaus Draeger Jul 16 '15 at 17:56

The idea of this exercise is to show that the pumping lemma is not a sure-fire method to prove that a language isn't regular. To show that, we need to come up with a language that (i) isn't regular, but (ii) cannot be proved not regular using the pumping lemma. This is the goal of your exercise.

The "pumping lemma method" for proving that a language $L$ isn't regular is a sort of game:

• The adversary gives you an integer $p$.
• You come up with a word $w \in L$ of length at least $p$.
• The adversary partitions the word into $w = xyz$, where $|xy| \leq p$ and $|y| \geq 1$.
• You come up with an integer $i$ such that $xy^iz \notin L$.

If you win this game then you have shown that $L$ is not regular. In order to show that the pumping lemma cannot be used to prove that $L$ is regular, you have to show that the adversary wins the game.

A winning strategy for you is, for each $p$, a word $w \in L$ of length at least $p$, and for each legal partition $w = xyz$, an integer $i$ such that $xy^i z \notin L$. This is how you apply the pumping lemma. A winning strategy for the adversary is an integer $p$ such that each word $w \in L$ of length at least $p$ can be legally partitioned as $w = xyz$ in such a way that $xy^i z \in L$ for all $i \geq 0$. This is your goal in this exercise.

If the pumping lemma doesn't work, what does work? There is a generalization of the pumping lemma in which you mark $p$ locations of the word $w$, and then the adversarial partition $w = xyz$ must satisfy (i) $xy$ contains at most $p$ marked locations, (ii) $y$ must contain at least one marked location. Sometimes this generalized version works when the usual one fails, but not always.

One method which is guaranteed to always work is the Myhill–Nerode criterion. If a language is not regular, you can always prove it (in principle) using the Myhill–Nerode theorem. In many cases it is also easier to apply than the pumping lemma, even when the latter does work. What pity that it is beyond the curricula of many courses!

• Great formulation of the problem. I am a little worried about the particular language $L$: it seems it actually does not satisfy the Pumping Lemma? The problem is that one may choose $i=0$ for a sequence of $a$'s in $a^{n+1}b^n$ with $n$ large. – Hendrik Jan Jul 17 '15 at 9:38
• Perhaps their version of the pumping lemma doesn't allow $i = 0$. – Yuval Filmus Jul 17 '15 at 13:43