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).
-
1$\begingroup$ 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$. $\endgroup$– Rick DeckerJul 16, 2015 at 14:33
-
1$\begingroup$ Please fix your title. It does not ask the question I think you want to ask. $\endgroup$– reinierpostJul 16, 2015 at 15:59
-
$\begingroup$ 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. $\endgroup$– Klaus DraegerJul 16, 2015 at 17:44
-
$\begingroup$ @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 $\endgroup$– Crysis85Jul 16, 2015 at 17:46
-
$\begingroup$ Yes, spotted that too late, sorry. I thought I had removed that comment quickly enough :) $\endgroup$– Klaus DraegerJul 16, 2015 at 17:56
1 Answer
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!
-
1$\begingroup$ 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. $\endgroup$ Jul 17, 2015 at 9:38
-
$\begingroup$ Perhaps their version of the pumping lemma doesn't allow $i = 0$. $\endgroup$ Jul 17, 2015 at 13:43