Prove that $\{w \mid \text{ w has even length and the first half of w has more 0s than the second half of w} \}$ is not regular?

Question

I have had some difficulties understanding proofs that a language is not regular using the Pumping Lemma, and now I need to prove that the following language

$$A = \{w \mid \text{ w has even length and the first half of w has more 0s than the second half of w} \}$$

is not regular.

I would start by assuming that $A$ is regular, and then I should pick a string in $A$ that for a certain $p$ (pumping length) would contradict the assumptions, i.e. $A$ is regular.

I think I first need to choose a string $s$, which of course must have even length, and the first part of that string must contain more $0$s than the second part. For example, $0001$ would be a string in $A$.

The length of $s$ must be greater or equal to $p$. Moreover, $s$ can be divided into three pieces, like $s = xyz$.

Now, how would I choose $s$? I saw that some proofs make $s$ depend on $p$. Is this strictly necessary, or is this just convenient, and why?

Could you please help me proceeding with the proof?

Answer 1

Defining $s$ partly in terms of $p$ is an easy way to ensure that $|s|\ge p$; this is necessary if we are to apply the pumping lemma. It also gives us some control over what the part $xy$ of the $xyz$ decomposition will look like.

Here I would start with an $s$ that just barely satisfies the condition putting it in $A$: $s=0^p10^{p-1}$. If $A$ were regular, there would be a decomposition $s=xyz$ such that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in A$ for each $k\ge 0$. Since $|xy|\le p$, we know that $xy$ is a string of zeroes: it’s part of the initial substring $0^p$ of $s$. Thus, there are $i,j$ such that $x=0^i$, $y=0^j$, $i+j\le p$, $i\ge 0$, and $j\ge 1$. (We know that $j\ge 1$, because $j=|y|\ge 1$.) This means that $z=0^{p-(i+j)}10^{p-1}$, and our decomposition is

$$s=x\color{red}y\color{blue}z=0^i\color{red}{0^j}\color{blue}{0^{p-(i+j)}10^{p-1}}\;.$$

Now what does $xy^kz$ look like for $k\ge 0$? It’s

$$xy^kz=0^i(0^j)^k0^{p-(i+j)}10^{p-1}=0^{i+kj+p-i-j}10^{p-1}=0^{p+(k-1)j}10^{p-1}\;.$$

In particular, when $k=0$ it’s $xz=0^{p-j}10^{p-1}$, where $j\ge 1$. Can you see why this word cannot be in $A$?

Answer 2

Yes this can language can be proven not regular using the pumping lemma. The strongest statement of the pumping lemma will work: if $L$ is regular, then there is a $p$ (equal to the number of states in a DFA accepting $L$), such that for any string $s\in L$, any substring $r$ of $s$ of length $\ge p$ has substrings that can be pumped. The proof is the same: given any substring $r$ of $s$ with $\lvert r\rvert\ge p$, the states that the DFA must traverse when "processing" $r$ are $p+1$ in number, so there must be repetition.)

If the $L$ in question were regular, let $p$ be the length given by the pumping lemma, and consider $s=0^{p+1}1^p$. Then $s\in L$. But some substring of the $1$s can be pumped, and the resulting strings will be in $L$. But clearly that's not true: the "pumped-up$ strings won't satisfy the definition of the language.