Skip to main content
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
Source Link

The Wikipedia article on the pumping lemma states:

We now pump $y$ up: $xy^2z$ has more instances of the letter $a$ than the letter $b$, since we have added some instances of $a$ without adding instances of $b$. Therefore, $xy^2z$ is not in $L$. We have reached a contradiction. Therefore, the assumption that $L$ is regular must be incorrect. Hence $L$ is not regular.

But this formal version of the lemma seems to differ: $$ \begin{align*} &(\forall L \subseteq \Sigma^*) \\ &\quad (\text{regular}(L) \Rightarrow \\ &\quad ((\exists p \geq 1)((\forall w \in L)((|w| \geq p) \Rightarrow \\ &\quad ((\exists x,y,z \in \Sigma^*)(w=xyz \land (|y| \geq 1 \land |xy| \leq p \land (\forall i \geq 0)(xy^iz \in L)))))))) \end{align*} $$ I thought there only has to "exist a combination of $x,y,z$" in order to be regular (as stated in this answerthis answer as well).

As far as I can see, the Wikipedia example only takes a look at one possible combination/example. Am I missing something obvious here?

The Wikipedia article on the pumping lemma states:

We now pump $y$ up: $xy^2z$ has more instances of the letter $a$ than the letter $b$, since we have added some instances of $a$ without adding instances of $b$. Therefore, $xy^2z$ is not in $L$. We have reached a contradiction. Therefore, the assumption that $L$ is regular must be incorrect. Hence $L$ is not regular.

But this formal version of the lemma seems to differ: $$ \begin{align*} &(\forall L \subseteq \Sigma^*) \\ &\quad (\text{regular}(L) \Rightarrow \\ &\quad ((\exists p \geq 1)((\forall w \in L)((|w| \geq p) \Rightarrow \\ &\quad ((\exists x,y,z \in \Sigma^*)(w=xyz \land (|y| \geq 1 \land |xy| \leq p \land (\forall i \geq 0)(xy^iz \in L)))))))) \end{align*} $$ I thought there only has to "exist a combination of $x,y,z$" in order to be regular (as stated in this answer as well).

As far as I can see, the Wikipedia example only takes a look at one possible combination/example. Am I missing something obvious here?

The Wikipedia article on the pumping lemma states:

We now pump $y$ up: $xy^2z$ has more instances of the letter $a$ than the letter $b$, since we have added some instances of $a$ without adding instances of $b$. Therefore, $xy^2z$ is not in $L$. We have reached a contradiction. Therefore, the assumption that $L$ is regular must be incorrect. Hence $L$ is not regular.

But this formal version of the lemma seems to differ: $$ \begin{align*} &(\forall L \subseteq \Sigma^*) \\ &\quad (\text{regular}(L) \Rightarrow \\ &\quad ((\exists p \geq 1)((\forall w \in L)((|w| \geq p) \Rightarrow \\ &\quad ((\exists x,y,z \in \Sigma^*)(w=xyz \land (|y| \geq 1 \land |xy| \leq p \land (\forall i \geq 0)(xy^iz \in L)))))))) \end{align*} $$ I thought there only has to "exist a combination of $x,y,z$" in order to be regular (as stated in this answer as well).

As far as I can see, the Wikipedia example only takes a look at one possible combination/example. Am I missing something obvious here?

Tweeted twitter.com/StackCompSci/status/835536048159608833
added 383 characters in body; edited title
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Lemma Regular Language - Exists Solution or For all? Quantification in pumping lemma for regular languages

The Wikipedia article https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Use_of_the_lemmaWikipedia article on the pumping lemma [0]
states:
 

We now pump y$y$ up: xy2z$xy^2z$ has more instances of the letter a$a$ than the letter b$b$, since we have added some instances of a$a$ without adding instances of b$b$. Therefore, xy2z$xy^2z$ is not in L$L$. We have reached a contradiction. Therefore, the assumption that L$L$ is regular must be incorrect. Hence L$L$ is not regular.

But regarding https://wikimedia.org/api/rest_v1/media/math/render/svg/9fe01e9c026e4c276384037200b7c166bcf7e6e6this formal version [1]
of the lemma seems to differ: $$ \begin{align*} &(\forall L \subseteq \Sigma^*) \\ &\quad (\text{regular}(L) \Rightarrow \\ &\quad ((\exists p \geq 1)((\forall w \in L)((|w| \geq p) \Rightarrow \\ &\quad ((\exists x,y,z \in \Sigma^*)(w=xyz \land (|y| \geq 1 \land |xy| \leq p \land (\forall i \geq 0)(xy^iz \in L)))))))) \end{align*} $$ I thought there only has to "existsexist a combination of x,y,z"$x,y,z$" in order to be regular (as stated in this answer as well: http://cs.stackexchange.com/a/18518/66316this answer [2]as well)
 .

As far as I can see, the Wikipedia example [0] only takes a look at one possible combination/example. Am I obviously missing something obvious here?

Lemma Regular Language - Exists Solution or For all?

The Wikipedia article https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Use_of_the_lemma [0]
states:
 

We now pump y up: xy2z has more instances of the letter a than the letter b, since we have added some instances of a without adding instances of b. Therefore, xy2z is not in L. We have reached a contradiction. Therefore, the assumption that L is regular must be incorrect. Hence L is not regular.

But regarding https://wikimedia.org/api/rest_v1/media/math/render/svg/9fe01e9c026e4c276384037200b7c166bcf7e6e6 [1]
I thought there only has to "exists a combination of x,y,z" in order to be regular (as stated in this answer as well: http://cs.stackexchange.com/a/18518/66316 [2])
 

As far as I can see, the example [0] only takes a look at one possible combination/example. Am I obviously missing something here?

Quantification in pumping lemma for regular languages

The Wikipedia article on the pumping lemma states:

We now pump $y$ up: $xy^2z$ has more instances of the letter $a$ than the letter $b$, since we have added some instances of $a$ without adding instances of $b$. Therefore, $xy^2z$ is not in $L$. We have reached a contradiction. Therefore, the assumption that $L$ is regular must be incorrect. Hence $L$ is not regular.

But this formal version of the lemma seems to differ: $$ \begin{align*} &(\forall L \subseteq \Sigma^*) \\ &\quad (\text{regular}(L) \Rightarrow \\ &\quad ((\exists p \geq 1)((\forall w \in L)((|w| \geq p) \Rightarrow \\ &\quad ((\exists x,y,z \in \Sigma^*)(w=xyz \land (|y| \geq 1 \land |xy| \leq p \land (\forall i \geq 0)(xy^iz \in L)))))))) \end{align*} $$ I thought there only has to "exist a combination of $x,y,z$" in order to be regular (as stated in this answer as well).

As far as I can see, the Wikipedia example only takes a look at one possible combination/example. Am I missing something obvious here?

added 7 characters in body
Source Link

The Wikipedia article https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languageshttps://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Use_of_the_lemma [0]
states:

We now pump y up: xy2z has more instances of the letter a than the letter b, since we have added some instances of a without adding instances of b. Therefore, xy2z is not in L. We have reached a contradiction. Therefore, the assumption that L is regular must be incorrect. Hence L is not regular.

But regarding https://wikimedia.org/api/rest_v1/media/math/render/svg/9fe01e9c026e4c276384037200b7c166bcf7e6e6 [1]
I thought there only has to "exists a combination of x,y,z" in order to be regular (as stated in this answer as well: http://cs.stackexchange.com/a/18518/66316 [2])

As far as I can see, the example [0] only takes a look at one possible combination/example. Am I obviously missing something here?

The Wikipedia article https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages [0]
states:

We now pump y up: xy2z has more instances of the letter a than the letter b, since we have added some instances of a without adding instances of b. Therefore, xy2z is not in L. We have reached a contradiction. Therefore, the assumption that L is regular must be incorrect. Hence L is not regular.

But regarding https://wikimedia.org/api/rest_v1/media/math/render/svg/9fe01e9c026e4c276384037200b7c166bcf7e6e6
I thought there only has to "exists a combination of x,y,z" in order to be regular (as stated in this answer as well: http://cs.stackexchange.com/a/18518/66316 )

As far as I can see, the example [0] only takes a look at one possible combination/example. Am I obviously missing something here?

The Wikipedia article https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Use_of_the_lemma [0]
states:

We now pump y up: xy2z has more instances of the letter a than the letter b, since we have added some instances of a without adding instances of b. Therefore, xy2z is not in L. We have reached a contradiction. Therefore, the assumption that L is regular must be incorrect. Hence L is not regular.

But regarding https://wikimedia.org/api/rest_v1/media/math/render/svg/9fe01e9c026e4c276384037200b7c166bcf7e6e6 [1]
I thought there only has to "exists a combination of x,y,z" in order to be regular (as stated in this answer as well: http://cs.stackexchange.com/a/18518/66316 [2])

As far as I can see, the example [0] only takes a look at one possible combination/example. Am I obviously missing something here?

Source Link
Loading