1
$\begingroup$

I have some questions about how a string can be divided into pieces according to the pumping lemma. I am learning from Michael Sipser’s book Introduction to the Theory of Computation, 3rd Edition. He states the pumping lemma as follows.

Pumping lemma If $A$ is a regular language, then there is a number $p$ (the pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:

  1. for each $i≥0, xy^i z∈A$,
  2. $|y|>0$,
  3. and $|xy|≤p$.

Sipser says that when $s$ is divided into $xyz$, either $x$ or $z$ may be $ε$, but not $y$ (condition 2).

He provides an example to show how the pumping lemma can be used to prove that the following language $B$ is not regular.

Let $B=\{0^n 1^n | ≥ 0\}$.

It is a proof by contradiction. He assumes $B$ is regular and presents three cases to show that it is not. In each case he splits a string $s$ from $B$ into $xyz$ in a different way. He chooses $s$ to be the string $0^p1^p$. In one case, Sipser lets $y$ consist only of 0s. Here are my questions:

  1. In this case, is it possible for $y$ to consist of $p$ 0s and for $x$ to be the empty string if $|xy|≤p$ (condition 3)?
  2. If so, do you agree that a case can be presented where $s$ is divided into $xyz$ such that $x=ε,y=0^p,z=1^p$?
  3. If so, do you agree that the string $xyyz$ contains more 0s than 1s?
  4. If so, do you agree that the string $xyyz$ is not in B?

I would greatly appreciate if you could answer all the questions in a numbered list format.

$\endgroup$

1 Answer 1

1
$\begingroup$

Here is the answer.

  1. Yes.
  2. Yes.
  3. Yes.
  4. Yes.
$\endgroup$
2
  • $\begingroup$ @billiam, were you expecting more detail in an answer? There is little room to add more detail to your clear and detailed question. $\endgroup$
    – John L.
    Nov 9, 2021 at 16:53
  • $\begingroup$ @JohnL. Your answer is fine, thank you. $\endgroup$
    – billiam
    Nov 9, 2021 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.