3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Raphael Apr 23 '12 at 22:24
  • 1
    $\begingroup$ check the "pumping lemma - step by step" answer cs.stackexchange.com/a/1051/157 $\endgroup$ – Ran G. Apr 24 '12 at 3:32
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – BrotherJack Apr 23 '12 at 19:42
  • $\begingroup$ Oops. Yes. I'll fix. $\endgroup$ – Dave Clarke Apr 23 '12 at 19:43
  • 1
    $\begingroup$ 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? $\endgroup$ – BrotherJack Apr 23 '12 at 19:51
  • 1
    $\begingroup$ Why not start with string $1^p0^{p+1}$? $\endgroup$ – Dave Clarke Apr 23 '12 at 19:55
  • $\begingroup$ I honestly don't know why I incremented beyond that. That seems far more logical. $\endgroup$ – BrotherJack Apr 23 '12 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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