Using the Pumping Lemma properly

Question

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

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

Answer 2

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.

Answer 3

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.