# Null Characters and Splitting the String in the Pumping Lemma

So I'm really struggling with the pumping lemma. I think most of my problems come from not understanding how you can and can't split the string in a pumping lemma question. Here is an example, take the problem prove that $L = \{w | w$ contains more $0$'s than $1$'s over the language $\{0,1\} \}$ is not regular via the pumping lemma.

So I choose the string $01^{p}0^{p}$. Since this is a regular language pumping lemma problem I know that:

1. for each $i > 0, xy^{i}z \in A$,
2. $|y^{i}| > 0$, and
3. $|xy| < p$

I am little uncertain about other possibilites though, such as if $x$, or $z$ can be null (obviously $y$ can't by condition 2). I assume that this isn't possible since I don't think the preceding or trailing whitespace is considered part of the string, but I'm not sure. Is it possible for $x$ or $z$ to be null?

• I am mildly concerned by the order of 1-3 and your leaving out the central binding of $xyz$. Is this an issue of writing down, or are you skipping steps?
– Raphael
Apr 23, 2012 at 22:24
• check the "pumping lemma - step by step" answer cs.stackexchange.com/a/1051/157 Apr 24, 2012 at 3:32

Yes, it is possible for $x$ or $z$ to be 'null', if by 'null' you mean the empty string. The empty string, $\epsilon$, is the string of length zero.
If the loop in the automaton (which is ultimately what the pumping lemma refers to) starts at the initial state and the initial state is also an accepting state, then strings of the form $y^i$ will be accepted, where $y$ is some string that will take you around the loop.
Whitespace plays no role in this theorem. Formal languages are defined over a given alphabet, in your case $\{0,1\}$. This is the only alphabet relevant for the question. There is no preceding or trailing whitespace when talking about the pumping lemma. Spaces, tabs, return characters play absolutely no role.
• Why not start with string $1^p0^{p+1}$? Apr 23, 2012 at 19:55