0
$\begingroup$

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

  • 0
    This is just a roundabout way of expressing the pumping lemma for regular languages. Over at http://cs.stackexchange.com it is a [reference question](http://cs.stackexchange.com/questions/1031/how-to-prove-that-a-language-is-not-regular), and references [wikipedia](http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages). – 2014-03-26

3 Answers 3

1

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.

  • 0
    I understand the proof well but something is being concatenated with the language so pumping lemma does not have any clause for that. – 2012-06-11
1

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.

0

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)