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

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.

• You haven't specified $s$... Using the condition $|xy| \leq d$, you can get more control on the location of $y$. – Yuval Filmus Oct 26 '20 at 14:12
• @YuvalFilmus $s$ is $0^d1^d$. Is my proof correct otherwise? (Is my method correct?) – NimaJan Oct 26 '20 at 14:19
• Per my comment above, there is really only a single option to consider, taking into account the condition $|xy| \leq d$. – Yuval Filmus Oct 26 '20 at 15:08
• @YuvalFilmus I still don't understand why there is only a single option to prove this. I'm sorry for the inconvenience. – NimaJan Oct 26 '20 at 17:22
• If $|s| \geq 2d$, $s = xyz$, and $|xy| \leq d$, then $xy$ belongs to the first half of the word. – Yuval Filmus Oct 26 '20 at 17:23

• 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| which entails that only the first case occurs.
But it is not wrong. If you want to ignore $$|xy| 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.
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.