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?

Improve this question
$\endgroup$
2
  • $\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
    Commented Apr 23, 2012 at 22:24
  • 1
    $\begingroup$ check the "pumping lemma - step by step" answer cs.stackexchange.com/a/1051/157 $\endgroup$
    – Ran G.
    Commented Apr 24, 2012 at 3:32

1 Answer 1

Reset to default
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.

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

Your Answer

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

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