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:
- for each $i≥0, xy^i z∈A$,
- $|y|>0$,
- 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:
- 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)?
- 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$?
- If so, do you agree that the string $xyyz$ contains more 0s than 1s?
- 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.