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.

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

2 Answers 2


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.

  • $\begingroup$ I understand it completely now. Thanks professor! $\endgroup$
    – NimaJan
    Commented Oct 27, 2020 at 13:02

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.