Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a question to solve but I am not even getting a direction to start or how to narrow down this problem. Please provide in your inputs.

Consider the following version of pumping lemma.

For any regular language $\mathcal L$, there is some $m≥1$ so that for every $y\in E^*$, if $|y|=m$, then there exist $u,x,v\in E^*$ so that:

  1. $y=uxv$
  2. $x \ne\epsilon$
  3. for all $z\in E^*$, $yz$ belongs to $\mathcal L$ if and only if $ux^ivz$ belongs to $\mathcal L$ for $i ≥0$

I need to prove that the pumping lemma holds. And language satisying i is regular

share|improve this question
    
I tried it but something extra has to be done. I have a feeling it is related to Myhill Nerode and right invariant property. I am not sure. –  Richa Sachdev Jun 11 '12 at 15:12
    
This is just a roundabout way of expressing the pumping lemma for regular languages. Over at cs.stackexchange.com it is a reference question, and references wikipedia. –  vonbrand Mar 26 at 21:37
add comment

3 Answers

You can indeed use the Myhill-Nerode theorem to show that a language that satisfies this pumping lemma is regular. For $u,v\in E^*$ write $u\sim_{\mathcal{L}} v$ iff for every $w\in E^*$, $uw\in\mathcal{L}$ iff $uw\in\mathcal{L}$. This is an equivalence relation on $E^*$, and the Myhill-Nerode theorem says that $\mathcal{L}$ is regular iff there are only finitely many $\sim_{\mathcal{L}}$-equivalence classes.

Suppose that $\mathcal{L}$ is not regular, so that there are infinitely many $\sim_{\mathcal{L}}$-classes, but $\mathcal{L}$ does satisfy this pumping lemma, with pumping number $m$. There are only finitely many words in $E^*$ of length less than $m$, so there is a $\sim_{\mathcal{L}}$-class $C$ such that every word in $C$ has length at least $m$. Let $w\in C$ have the shortest length of any word in $C$, and let $w=uv$, where $|u|=m$. Now apply this pumping lemma to $u$ to get a contradiction.

share|improve this answer
add comment

This is very similar to the standard statement of the pumping lemma. Since you said you don't know how to begin, I suggest that you start by carefully review ing the proof of the standard pumping lemma that you will find in your textbook.

Then compare this statement to the standard pumping lemma to see exactly ehat the differences are, and see if you can make a small change to the standard proof to get the theorem that you need to prove here.

If you didn't understand the proof in your book, get a different book. The book by Michael Sipser is pretty good.


(Appending my comment.)

In the ordinary pumping lemma, the $uxv$ string gets the automaton into an accepting state. Here, it might not. It only gets the automaton into a state, say $S$, from which some additional input $z$ might get it to an accepting state. But if $uxv$ gets it to $S$, and $x$ goes around a loop, then $ux^iv$ will go around the loop $i$ times and get the automaton to $S$ also. And since $uxv$ gets the automaton to $S$, and $ux^iv$ gets it to $S$ also, then $ux^ivz$ must get it to the same state as $uxvz$. So if the automaton accepts $uxvz$, for some $z$, it must accept $ux^ivz$ also, and vice versa.

share|improve this answer
    
I understand the proof well but something is being concatenated with the language so pumping lemma does not have any clause for that. –  Richa Sachdev Jun 11 '12 at 15:14
add comment

pumping lemma provides you with a 'p' such that if $a \in L$, $\exists u,x,v$ such that a = uxv ,$|ux|\leqslant p$ and $ux^{i}v$ belong to $L \forall i.$

choose m to be that p. then for all y, z such that |y|= m if $yz \in L$, then yz = uxvz (since $|ux| \leqslant m$ by pumping lemma)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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