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$ – Yuval Filmus Oct 26 '20 at 14:12
  • $\begingroup$ @YuvalFilmus $s$ is $0^d1^d$. Is my proof correct otherwise? (Is my method correct?) $\endgroup$ – NimaJan Oct 26 '20 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$ – Yuval Filmus Oct 26 '20 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 Oct 26 '20 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$ – Yuval Filmus Oct 26 '20 at 17:23

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 Oct 27 '20 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, privacy policy and cookie policy

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