2
$\begingroup$

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

  • 0
    Yes, sorry I forgot to put that in the op. Editing it now2012-02-27

3 Answers 3

1

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$?

  • 0
    @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](http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#General_version_of_pumping_lemma_for_regular_languages); the proof is essentially the same as for the simpler form.2012-02-27
1

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.

0

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.