Skip to main content
Length condition on $s$
Source Link
vonbrand
  • 14.1k
  • 3
  • 41
  • 52

You cannot proceed in this way. The Pumping Lemma for regular languages tells us that if a language $L$ is regular, then there exists a $p \geq 0$ such that every $s \in L$ such that $\lvert s \rvert \ge p$ can be partitioned as $s = xyz$ in such a way that

  1. $|y| > 0$
  2. $|xy| \leq p$
  3. $xy^iz \in L$ for all $i \geq 0$

To show that a language $L$ fails to be regular, we must show that for any choice of $p$ we can find an $s \in L$ such that every possible partition of $s$ will violate one or more of the above three conditions.

In your attempted solution, your candidate string has length $2p$. Condition 2 tells us that $y$ must occur within the first $p$ symbols and must therefore consist of $0$s only.

If condition 1 is to also hold, $y$ must be non-empty. But then $xy^2z \notin L$, as this string will have more occurrences of $0$s than of $1$s. So condition 3 cannot hold, if we require conditions 1 and 2 to hold.

Your misunderstanding is one that students often make; they assume that the partition must be one that somehow "magically pairs off" the symbols according to its shape: If the candidate string has a part consisting of $0$s followed by a part consisting of $1$s, then the initial substring $x$ must somehow consist of all the $0$s. This is not the case. That you then also assume that $x$ is empty, shows an internal contradiction: At the same time you claim that $x$ must consist of all $0$s and that $x$ can be chosen to be any string whatsoever, in this case the empty string.

You cannot proceed in this way. The Pumping Lemma for regular languages tells us that if a language $L$ is regular, then there exists a $p \geq 0$ such that every $s \in L$ can be partitioned as $s = xyz$ in such a way that

  1. $|y| > 0$
  2. $|xy| \leq p$
  3. $xy^iz \in L$ for all $i \geq 0$

To show that a language $L$ fails to be regular, we must show that for any choice of $p$ we can find an $s \in L$ such that every possible partition of $s$ will violate one or more of the above three conditions.

In your attempted solution, your candidate string has length $2p$. Condition 2 tells us that $y$ must occur within the first $p$ symbols and must therefore consist of $0$s only.

If condition 1 is to also hold, $y$ must be non-empty. But then $xy^2z \notin L$, as this string will have more occurrences of $0$s than of $1$s. So condition 3 cannot hold, if we require conditions 1 and 2 to hold.

Your misunderstanding is one that students often make; they assume that the partition must be one that somehow "magically pairs off" the symbols according to its shape: If the candidate string has a part consisting of $0$s followed by a part consisting of $1$s, then the initial substring $x$ must somehow consist of all the $0$s. This is not the case. That you then also assume that $x$ is empty, shows an internal contradiction: At the same time you claim that $x$ must consist of all $0$s and that $x$ can be chosen to be any string whatsoever, in this case the empty string.

You cannot proceed in this way. The Pumping Lemma for regular languages tells us that if a language $L$ is regular, then there exists a $p \geq 0$ such that every $s \in L$ such that $\lvert s \rvert \ge p$ can be partitioned as $s = xyz$ in such a way that

  1. $|y| > 0$
  2. $|xy| \leq p$
  3. $xy^iz \in L$ for all $i \geq 0$

To show that a language $L$ fails to be regular, we must show that for any choice of $p$ we can find an $s \in L$ such that every possible partition of $s$ will violate one or more of the above three conditions.

In your attempted solution, your candidate string has length $2p$. Condition 2 tells us that $y$ must occur within the first $p$ symbols and must therefore consist of $0$s only.

If condition 1 is to also hold, $y$ must be non-empty. But then $xy^2z \notin L$, as this string will have more occurrences of $0$s than of $1$s. So condition 3 cannot hold, if we require conditions 1 and 2 to hold.

Your misunderstanding is one that students often make; they assume that the partition must be one that somehow "magically pairs off" the symbols according to its shape: If the candidate string has a part consisting of $0$s followed by a part consisting of $1$s, then the initial substring $x$ must somehow consist of all the $0$s. This is not the case. That you then also assume that $x$ is empty, shows an internal contradiction: At the same time you claim that $x$ must consist of all $0$s and that $x$ can be chosen to be any string whatsoever, in this case the empty string.

Source Link
Hans Hüttel
  • 2.5k
  • 10
  • 17

You cannot proceed in this way. The Pumping Lemma for regular languages tells us that if a language $L$ is regular, then there exists a $p \geq 0$ such that every $s \in L$ can be partitioned as $s = xyz$ in such a way that

  1. $|y| > 0$
  2. $|xy| \leq p$
  3. $xy^iz \in L$ for all $i \geq 0$

To show that a language $L$ fails to be regular, we must show that for any choice of $p$ we can find an $s \in L$ such that every possible partition of $s$ will violate one or more of the above three conditions.

In your attempted solution, your candidate string has length $2p$. Condition 2 tells us that $y$ must occur within the first $p$ symbols and must therefore consist of $0$s only.

If condition 1 is to also hold, $y$ must be non-empty. But then $xy^2z \notin L$, as this string will have more occurrences of $0$s than of $1$s. So condition 3 cannot hold, if we require conditions 1 and 2 to hold.

Your misunderstanding is one that students often make; they assume that the partition must be one that somehow "magically pairs off" the symbols according to its shape: If the candidate string has a part consisting of $0$s followed by a part consisting of $1$s, then the initial substring $x$ must somehow consist of all the $0$s. This is not the case. That you then also assume that $x$ is empty, shows an internal contradiction: At the same time you claim that $x$ must consist of all $0$s and that $x$ can be chosen to be any string whatsoever, in this case the empty string.