# 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? Commented Apr 23, 2012 at 22:24
• check the "pumping lemma - step by step" answer cs.stackexchange.com/a/1051/157 Commented Apr 24, 2012 at 3:32

## 1 Answer

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.

• Do you mean x and z? I'm under the assumption that property 2 requires that y not be the empty string as it has to be greater than 0. If this is true I assume that my answer would be wrong as you could simply divide the string x = null, y =0, and z = 1^p0^p Commented Apr 23, 2012 at 19:42
• Oops. Yes. I'll fix. Commented Apr 23, 2012 at 19:43
• I assume that you would have to choose a string like 1^(p+1)0^(p+2) so that there is no way to place 0's in y as |xy| can't be greater than p, and there has to be something in y. It seems to me this arrangement would require that p-1 1's are in x and y and the rest of the string is in z. Would there be any other way to divide the string? Is this legal? Commented Apr 23, 2012 at 19:51
• Why not start with string $1^p0^{p+1}$? Commented Apr 23, 2012 at 19:55
• I honestly don't know why I incremented beyond that. That seems far more logical. Commented Apr 23, 2012 at 19:58