Modified Pumping Lemma

[mathmari]

Hi!
Let L be the language, which has an infinite number of words, then there are words [tex]x,y,z \epsilon \Sigma ^{*}[/tex], so that [tex]|xz|\leq |\Sigma_{k}|[/tex], and each word [tex]xy^{(i)}z, i\geq0 [/tex] is in L.
How could we prove this modified Pumping Lemma?

 

[mathmari]

What is the relation between the length of [tex] |xz| [/tex] and the number of the states?

 

[Evgeny.Makarov]

Let L be the language, which has an infinite number of words

Any infinite language whatsoever?

then there are words [tex]x,y,z \epsilon \Sigma ^{*}[/tex], so that [tex]|xz|\leq |\Sigma_{k}|[/tex]

What is $\Sigma_k$?

and each word [tex]xy^{(i)}z, i\geq0 [/tex] is in L.

Just to be sure: $y^{(i)}$ is the concatenation of $i$ copies of $y$? I saw this denoted by $y^i$ before, and since in calculus $y^i$ and $y^{(i)}$ are two different things, I am just being careful...

How could we prove this modified Pumping Lemma?

Since this relates to various variants of the pumping lemma, what is the standard variant and can we use it?

 

[mathmari]

Any infinite language whatsoever?

With this lemma we want to show that a language is not regular.

What is $\Sigma_k$?

It is the set of the states.

Just to be sure: $y^{(i)}$ is the concatenation of $i$ copies of $y$? I saw this denoted by $y^i$ before, and since in calculus $y^i$ and $y^{(i)}$ are two different things, I am just being careful...

I think it is the concatenation of $i$ copies of $y$.

Since this relates to various variants of the pumping lemma, what is the standard variant and can we use it?

The standard variant of the Pumping Lemma is:
Let L be the language of the automaton M, which has an infinite number of words, then there are words $x,y,z \epsilon \Sigma^{*}$, so that each word $xy^{(i)}z \epsilon L$.

 

[mathmari]

With this lemma we want to show that a language is not regular.

It is the set of the states.

I think it is the concatenation of $i$ copies of $y$.


The standard variant of the Pumping Lemma is:
Let L be the language of the automaton M, which has an infinite number of words, then there are words $x,y,z \epsilon \Sigma^{*}$, so that each word $xy^{(i)}z \epsilon L$.

So, at the modified lemma, $|xz| \leq |\Sigma_{k}|$ must also be satisfied..

 

[Evgeny.Makarov]

What is the relation between the length of $|xz|$ and the number of the states?

Let $n$ be the number of states of the automaton. Take a word $w\in L$ whose length is at least $n$ and feed it to the automaton. Then some state $s$ is visited at least twice. Split $w$ so that $x$ is read before the first visit to $s$, $z$ is read after the last visit to $s$ and $y$ is everything in between. Then $xy^iz\in L$ for all $i$. However, it does not follow that $|xz|\le n$. In the best case, the states visited reading $x$ are different from those visited reading $z$; then indeed $|xz|\le n$, but this does not have to happen. Another choice of $s$ may be needed.

By the way, are you sure it's $|xz|\le n$ and not $|xy|\le n$?

 

[mathmari]

Let $n$ be the number of states of the automaton. Take a word $w\in L$ whose length is at least $n$ and feed it to the automaton. Then some state $s$ is visited at least twice. Split $w$ so that $x$ is read before the first visit to $s$, $z$ is read after the last visit to $s$ and $y$ is everything in between. Then $xy^iz\in L$ for all $i$. However, it does not follow that $|xz|\le n$. In the best case, the states visited reading $x$ are different from those visited reading $z$; then indeed $|xz|\le n$, but this does not have to happen. Another choice of $s$ may be needed.

By the way, are you sure it's $|xz|\le n$ and not $|xy|\le n$?

I am asked to show that $|xz|\le n$..

 

[mathmari]

Is this sure that we cannot conclude that $|xz| \leq n$ ?

 

[Evgeny.Makarov]

I have to think about this.

 

[mathmari]

I am also asked to apply this lemma at an exercise.
Let the language be $L=\{ww|w \epsilon \{a,b\}^{*}\}$. To show that this language is not regular using the lemma above,what can I do? Do I have to take a specific word and apply this?

 

[Evgeny.Makarov]

At this point, I can only tell you how this is proved using standard pumping lemma. There are two differences with your version: first, it uses $|xy|\le n$ and not $|xz|\le n$ and, second, it says that every sufficiently long word (longer than the number of states) can be decomposed into $xyz$, not that there exists such a word. You can see a proof of this lemma in Wikipedia.

So, if $L$ is regular, then $a^kb^ka^kb^k\in L$ for every $k$. If $k>n$, then $xy$ and thus $y$ must consist of $a$s only. Pumping in $a$'s will break the balance between the first and second segments of $a$s, i.e., the number of $a$s in the two segments will be different and thus the word will no longer be a square.

 

[mathmari]

I found the proof of this version of Pumping Lemma in a textbook.

At at the path(from the initial state $I$ to an accepting state $T$) that generates a very large word, a state $K$ wil be repeated and the path has the form:
$I \to ... \to K ... \to K \to ... \to T$
If we delete the part $ K \to ... \to K$ the path still generates an accepting word.
If at the sub-path $ I \to ... \to K $ and $ K \to ... \to T $ there is no other common state $L$ (besides $K$), then we have finished: we set $x=I \to ... \to K$, $z=K \to ... \to T $ and $y=K\to ... \to K$. If there is a common state $L$ then we delete the part $K \to ... \to K$ and we continue with the path $ I \to ... \to L \to ... \to K \to ... \to L \to... \to T$.

I'm a little confused...Could you explain me the second case, when there is a common state $L$ ?

 

[Evgeny.Makarov]

Could you explain me the second case, when there is a common state $L$ ?

Then we replace the middle path $K\to\dots\to K$ by just one state $K$. By assumption, there is a state $L$ that belongs to the first part $I\to\dots\to K$ and to the last part $K\to\dots\to T$. Therefore, after removing the middle part the path looks like \[
I \to\dots \to L \to\dots \to K \to\dots \to L \to\dots \to T.\] Then we apply the whole procedure again, and $L$ plays the role that $K$ played.

 

[mathmari]

Then we replace the middle path $K\to\dots\to K$ by just one state $K$. By assumption, there is a state $L$ that belongs to the first part $I\to\dots\to K$ and to the last part $K\to\dots\to T$. Therefore, after removing the middle part the path looks like \[
I \to\dots \to L \to\dots \to K \to\dots \to L \to\dots \to T.\] Then we apply the whole procedure again, and $L$ plays the role that $K$ played.

I got!! Thank you for explaining to me!!!