Welcome to our community

Be a part of something great, join today!

Modified Pumping Lemma

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,118
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,118
What is the relation between the length of [tex] |xz| [/tex] and the number of the states?
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,118
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,118
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,118
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$..
 
Last edited:

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,118
Is this sure that we cannot conclude that $|xz| \leq n$ ? :eek:
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
I have to think about this.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,118
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,118
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,118
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!!! :eek: