Using the Pumping Lemma to show that the language of all strings of even length having no $0s$ in their second half is not regular

Question

I'm struggling with finding a starting string $s$ to prove using the Pumping Lemma that language $$L = \{w \mid w\text{ has even length and the second half of $w$ does not contain any $0$s}\}$$ is not regular. Any suggestions?

Answer 1

Assume $L$ is regular, with pumping length $n$. Consider $0^n1^n\in L$. Then $0^n1^n=uvw$ with $|uv|\le n$ (so consisting only of $0$s), and $|v|>0$ and $uv^kw\in L$ for all $k\in\Bbb N_0$. Then $uv^2w$ has length $>2n$, but $0$ occurs among the last $n+1$.

Answer 2

Any string of the language you choose will suffice. Just remember that for a partition of the string $s=uvw$ to be used with the pumping lemma, it has to be true that $|uv|\leq n$ ($n$ is the pumping number of $L$). Think about what would then happen to strings with $|s|>2n$.

(You only wanted a hint so I will not answer your question completely.)

Edit as a response to your comment, because it would be to long for another comment:

The pumping lemma states that $uv^iw\in L$ must hold true for all $s=uvw$ with $|s|>n$ for some $n$ which depends on the language. It also has the restriction that $|uv|\leq n$, so "in words":

Say that the pumping number of $L$ is, for example, $n=5$. Then the pumping lemma states that for any word longer than 5, you have to be able to choose a suffix of the first five symbols and repeat it an arbitrary number of times.

So for example, in the word $s="0000011111"$ (which is longer than five) you must be able to choose a suffix of the first five symbols (all zeros) and repeat it arbitrary ("pump" it). Since there are only zeros, you may choose what you want (for example, $v="00"$), but the problem is that as the word $uv^iw$ gets longer, the number of ones do not increase, so $uv^2w="000000011111$ would already not be part of the language anymore because the second half contains zeros.

This same thought process can be made for the general case and thus you are able to disproof that $L$ is regular.