Skip to main content
added 292 characters in body
Source Link
GoodDeeds
  • 851
  • 5
  • 14

You are right that the pumping lemma requires only some $x,y,z$ to exist, for every string whose length is greater than the pumping length, that satisfy the three conditions. However, when you attempt to show that a language is not regular, you use the method of contradiction, which makes use of the negation of the consequent of the implication in the pumping lemma.

The pumping lemma states that

If a language $L$ is regular, then there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

  1. $xy^iz\in L$ for all $i\ge 0$
  2. $|y|\gt 0$
  3. $|xy|\le p$

Let $p$ be the statement: The language $L$ is regular.

Let $q$ be the statement: Given a language $L$, there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

  1. $xy^iz\in L$ for all $i\ge 0$
  2. $|y|\gt 0$
  3. $|xy|\le p$

The pumping lemma states that $p\implies q$.


To show that a language $L$ is not regular using the pumping lemma, you first assume that $L$ is regular, i.e., $p$ is true.

Then, you try to show that $\neg q$ is true. From the pumping lemma, as $p\implies q$, the contrapositive $\neg q\implies \neg p$ also holds. So, if you can show that $\neg q$ is true, it implies that $\neg p$ is true. From the assumption that $p$ is true, we have both $p$ and $\neg p$ to be true, which is a contradiction.

Now, let's see what is $\neg q$. We need to negate the statement $q$, which gives, $\neg q$:

Given a language $L$, for all $p\gt 0$, there exists string $s\in L$ such that $|s|\ge p$, and for all ways to split $s$ in the form $x,y,z$, at least one of the following conditions don't hold:

  1. $xy^iz\in L$ for all $i\ge 0$
  2. $|y|\gt 0$
  3. $|xy|\le p$

Now, you can see from here, that in the negation, the statement must be true irrespective of how you split $s$ into $x,y,z$. So, for any arbitrary $p$, if you can find any one string $s$ such that for every way to split it in the form $x,y,z$, at least one of the three conditions are false, it implies that the language is not regular.

The only place where "one possible example" has been used is in the choice of $s$, which is correct as you can see from the statement. No assumption has been made in how $s$ splits into $x,y,z$, and yet, it has been shown that at least one of the conditions becomes false. So, for a given $s$, all $x,y,z$ have been indeed considered.

It may appear that the $|y|\gt 0$ and $|xy|\le p$ make the choice of $x,y,z$ a specific choice, however, this must be true if conditions 2. and 3. are to be true - if they were not, we trivially reach a contradiction as we need only any one of the three conditions (at least) to be false.

You are right that the pumping lemma requires only some $x,y,z$ to exist, for every string whose length is greater than the pumping length, that satisfy the three conditions. However, when you attempt to show that a language is not regular, you use the method of contradiction, which makes use of the negation of the consequent of the implication in the pumping lemma.

The pumping lemma states that

If a language $L$ is regular, then there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

  1. $xy^iz\in L$ for all $i\ge 0$
  2. $|y|\gt 0$
  3. $|xy|\le p$

Let $p$ be the statement: The language $L$ is regular.

Let $q$ be the statement: Given a language $L$, there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

  1. $xy^iz\in L$ for all $i\ge 0$
  2. $|y|\gt 0$
  3. $|xy|\le p$

The pumping lemma states that $p\implies q$.


To show that a language $L$ is not regular using the pumping lemma, you first assume that $L$ is regular, i.e., $p$ is true.

Then, you try to show that $\neg q$ is true. From the pumping lemma, as $p\implies q$, the contrapositive $\neg q\implies \neg p$ also holds. So, if you can show that $\neg q$ is true, it implies that $\neg p$ is true. From the assumption that $p$ is true, we have both $p$ and $\neg p$ to be true, which is a contradiction.

Now, let's see what is $\neg q$. We need to negate the statement $q$, which gives, $\neg q$:

Given a language $L$, for all $p\gt 0$, there exists string $s\in L$ such that $|s|\ge p$, and for all ways to split $s$ in the form $x,y,z$, at least one of the following conditions don't hold:

  1. $xy^iz\in L$ for all $i\ge 0$
  2. $|y|\gt 0$
  3. $|xy|\le p$

Now, you can see from here, that in the negation, the statement must be true irrespective of how you split $s$ into $x,y,z$. So, for any arbitrary $p$, if you can find any one string $s$ such that for every way to split it in the form $x,y,z$, at least one of the three conditions are false, it implies that the language is not regular.

The only place where "one possible example" has been used is in the choice of $s$, which is correct as you can see from the statement. No assumption has been made in how $s$ splits into $x,y,z$, and yet, it has been shown that at least one of the conditions becomes false. So, for a given $s$, all $x,y,z$ have been indeed considered.

You are right that the pumping lemma requires only some $x,y,z$ to exist, for every string whose length is greater than the pumping length, that satisfy the three conditions. However, when you attempt to show that a language is not regular, you use the method of contradiction, which makes use of the negation of the consequent of the implication in the pumping lemma.

The pumping lemma states that

If a language $L$ is regular, then there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

  1. $xy^iz\in L$ for all $i\ge 0$
  2. $|y|\gt 0$
  3. $|xy|\le p$

Let $p$ be the statement: The language $L$ is regular.

Let $q$ be the statement: Given a language $L$, there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

  1. $xy^iz\in L$ for all $i\ge 0$
  2. $|y|\gt 0$
  3. $|xy|\le p$

The pumping lemma states that $p\implies q$.


To show that a language $L$ is not regular using the pumping lemma, you first assume that $L$ is regular, i.e., $p$ is true.

Then, you try to show that $\neg q$ is true. From the pumping lemma, as $p\implies q$, the contrapositive $\neg q\implies \neg p$ also holds. So, if you can show that $\neg q$ is true, it implies that $\neg p$ is true. From the assumption that $p$ is true, we have both $p$ and $\neg p$ to be true, which is a contradiction.

Now, let's see what is $\neg q$. We need to negate the statement $q$, which gives, $\neg q$:

Given a language $L$, for all $p\gt 0$, there exists string $s\in L$ such that $|s|\ge p$, and for all ways to split $s$ in the form $x,y,z$, at least one of the following conditions don't hold:

  1. $xy^iz\in L$ for all $i\ge 0$
  2. $|y|\gt 0$
  3. $|xy|\le p$

Now, you can see from here, that in the negation, the statement must be true irrespective of how you split $s$ into $x,y,z$. So, for any arbitrary $p$, if you can find any one string $s$ such that for every way to split it in the form $x,y,z$, at least one of the three conditions are false, it implies that the language is not regular.

The only place where "one possible example" has been used is in the choice of $s$, which is correct as you can see from the statement. No assumption has been made in how $s$ splits into $x,y,z$, and yet, it has been shown that at least one of the conditions becomes false. So, for a given $s$, all $x,y,z$ have been indeed considered.

It may appear that the $|y|\gt 0$ and $|xy|\le p$ make the choice of $x,y,z$ a specific choice, however, this must be true if conditions 2. and 3. are to be true - if they were not, we trivially reach a contradiction as we need only any one of the three conditions (at least) to be false.

Source Link
GoodDeeds
  • 851
  • 5
  • 14

You are right that the pumping lemma requires only some $x,y,z$ to exist, for every string whose length is greater than the pumping length, that satisfy the three conditions. However, when you attempt to show that a language is not regular, you use the method of contradiction, which makes use of the negation of the consequent of the implication in the pumping lemma.

The pumping lemma states that

If a language $L$ is regular, then there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

  1. $xy^iz\in L$ for all $i\ge 0$
  2. $|y|\gt 0$
  3. $|xy|\le p$

Let $p$ be the statement: The language $L$ is regular.

Let $q$ be the statement: Given a language $L$, there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

  1. $xy^iz\in L$ for all $i\ge 0$
  2. $|y|\gt 0$
  3. $|xy|\le p$

The pumping lemma states that $p\implies q$.


To show that a language $L$ is not regular using the pumping lemma, you first assume that $L$ is regular, i.e., $p$ is true.

Then, you try to show that $\neg q$ is true. From the pumping lemma, as $p\implies q$, the contrapositive $\neg q\implies \neg p$ also holds. So, if you can show that $\neg q$ is true, it implies that $\neg p$ is true. From the assumption that $p$ is true, we have both $p$ and $\neg p$ to be true, which is a contradiction.

Now, let's see what is $\neg q$. We need to negate the statement $q$, which gives, $\neg q$:

Given a language $L$, for all $p\gt 0$, there exists string $s\in L$ such that $|s|\ge p$, and for all ways to split $s$ in the form $x,y,z$, at least one of the following conditions don't hold:

  1. $xy^iz\in L$ for all $i\ge 0$
  2. $|y|\gt 0$
  3. $|xy|\le p$

Now, you can see from here, that in the negation, the statement must be true irrespective of how you split $s$ into $x,y,z$. So, for any arbitrary $p$, if you can find any one string $s$ such that for every way to split it in the form $x,y,z$, at least one of the three conditions are false, it implies that the language is not regular.

The only place where "one possible example" has been used is in the choice of $s$, which is correct as you can see from the statement. No assumption has been made in how $s$ splits into $x,y,z$, and yet, it has been shown that at least one of the conditions becomes false. So, for a given $s$, all $x,y,z$ have been indeed considered.