Language of all even-length words with no 1's in left half

Question

Consider the following language:

$$L=\{w \in \textstyle\Sigma_1 ^*\mid|w| \text{ is even and 1's can only occur in the second half of $w$}\},$$

where $\Sigma_1 = \{0,1\}$.

I need to show that this is not regular. I tried to prove this with the pumping lemma.

Imagine that there exists a pumping length $d$, and consider the string $s=0^d1^d$. If we choose $s=xyz$ arbitrarily with $|y| > 0$, we will have three options.

1. $y$ can be in the first half of the string.

2. $y$ can be in the second half of the string.

3. $y$ can contain the first and second half of the string.

In the last option, $y$ can only be in the following form: $0(0)^+$ or $(0)^+(1)^+$. (Here $^+$ means Kleene plus.)

For the last form ($(0)^+(1)^+$), we see that $xyyz$ will have a $1$ in the first half, which is not in $L$. Consequently, $L$ cannot be regular.

Answer 1

Two points:

• the reasoning is incomplete: you need to show that pumping $y$ in the two first cases also leads to elements outside $L$
• the reasoning does not use $ |xy|<d$ which entails that only the first case occurs.

But it is not wrong. If you want to ignore $|xy|<d $ then you need to argue the three cases. The first case holds because deleting $y$ creates a string of odd length or one in which a $1$ appears in the first half. The second case holds because if we pump $y$ $ n >1$ times a $1$ will flow into the first part.

Answer 2

Take $s = 0^d 1^d$. Given a decomposition $s = xyz$ such that $|xy|\leq d$ and $y \neq \epsilon$, you can check that $xy^0z \notin L$, hence $L$ is not regular.