# Pumping lemma shows non-regular language, assignment suggests it is regular

In the assignment it asks us to show that $$L = \{0^kw0^k \mid k \ge 1 \text{ and } w \in \{0, 1\}^\ast\}$$ is regular (suggesting that it is in fact regular).

I don't believe that it is, so I tried using the pumping lemma to show this and it appears to have worked. I need help with where I am going wrong.

Suppose $L$ is regular.

Let $p$ be the pumping constant for $L$.

Let $s = 0^{p+1}w0^{p+1}$.>

By the pumping lemma, $s = xyz$, $|xy| \le p$, $y \ne \epsilon$, and $xy^kz \in L, k \ge 0$

Due to the first requirement, $|xy| \le p$, $y$ is entirely made up of 0's. By the third requirement, $xy^kz \in L, k \ge 0$, the string $xz \in L$. $xz = 0^{p - |y|}w0^{p+1}$, since $|y| > 0$, $p - |y| \ne |p + 1|$. Therefore $xz \notin L$, which is a contradiction. Therefore $L$ is non-regular.

I can't immediately think of a DFA, NFA, or regular expression to represent the language, since it can't store how many 0's have been made in the initial set of 0's, so I'm not really sure how to show that it is regular.

A regular expression describing this language is $$0(0|1)^*0$$ Any extra $0$'s can be absorbed into $w$, so the only distinguishing quality is that it starts and ends with a $0$.
• Your mistake is saying that $0^{p-|y|}w0^{p+1}$ doesn't belong to $L$. Infact, you can write it as $0v0$, with $v=0^{p-|y|-1}w0^p$, and you conclude that it belongs to $L$ (using $k=1$) Commented Feb 2, 2015 at 2:00