Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm working through some of the questions in a textbook and I'm stuck on the following pumping lemma question.

$$L_1 = \Big\{w \in \{0,1\}^* \mid\text{ every prefix of }w\text{ has at least as many zeroes as ones}\Big\}$$

I've worked through some very easy examples but this one has me stumped. Any tips on where to go with this?

EDIT: The goal of this question is to prove that $L_1$ is not regular

share|improve this question
    
Yes, sorry I forgot to put that in the op. Editing it now –  Chris Feb 27 '12 at 7:00
add comment

3 Answers

The pumping lemma for regular languages gives you a positive integer $p$ such that if $uwv\in L_1$, and $|w|\ge p$, then $w$ can be written as $w=xyz$, where $|xy|\le p$, $|y|\ge 1$, and $uxy^nzv\in L_1$ for every non-negative integer $n$. What happens if you apply this lemma to the word $0\,^p1^p$, taking $u=0\,^p$, $w=1^p$, and $v=\lambda$?

share|improve this answer
    
Isn't the adversary supposed to choose the split? What am I missing? Thanks. –  Aryabhata Feb 27 '12 at 7:29
    
@Aryabhata: You’re missing the fact that it’s $w$ that’s being split, not $uwv$. Since $w$ is all $1$’s, it doesn’t matter how it gets split. I’m using the general form of the pumping lemma; the proof is essentially the same as for the simpler form. –  Brian M. Scott Feb 27 '12 at 8:22
    
Ok. Thank you.... –  Aryabhata Feb 27 '12 at 17:11
add comment

Note that if $L_1$ were regular, then it would have a pumping length, say $p \geq 1$. This means that every string $w$ belonging to $L_1$ of length at least $p$ (i.e., $|w| \geq p$) can be split up as $w = xyz$ where

  1. $|y| \geq 1$;
  2. $|xy| \leq p$; and
  3. give any integer $i \geq 0$ the string $xy^iz$ belong to $L_1$.

Consider the string $0^p1^p$. Clearly this belong to $L_1$ and has length $p+p$, so it can be split up as $0^p1^p = xyz$ as above. Note that since $| xy | \leq p$, it must be that $y$ (and $x$ as well) consists solely of $0$s. Finally, consider what happens when we pump $y$ zero times.

share|improve this answer
add comment

A pump-less answer:

For any $0 \le n < m$, the string $0^m1^m$ is in $L_1$, but $0^n1^m$ is not. Therefore the set of subwords that can follow $0^n$ is different from the set of subwords that can follow $0^m$. But this means that a deterministic automaton that recognizes $L_1$ will need to be in different states when it has read $0^n$ for different $n$. This requires an infinity of states, so $L_1$ is not recognized by any DFA, so it is not regular.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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