Computer Science – Is the Pumping Lemma Properly Applied to Prove $L = \{ 0^i1^{i+j}0^i \mid i, j > 0 \}$?

computer sciencepumping-lemmaregular-language

The problem is to prove whether $L = \{0^i1^{i+j}0^i \mid i, j > 0\}$ is regular or not.

I've used the Pumping Lemma with a string $s = 0^p1^{2p}0^p$, however I do not know I can choose such string (yet the language description does not state that $i \neq j$ nor the opposite). With this string, we can say that $\vert s \vert \geq p$, so $s$ can be split in three pieces as $s = xyz$.

To satisfy the second ($\vert y \vert > 0$) and third ($\vert xy \vert \leq p$) condition of the lemma, $y$ must only contain $0$'s, and therefore: $x = \varepsilon$, $y = 0^p$ and $z = 1^{2p}0^p$.

Finally, if we pump $y$ and check whether it is still in $L$, we clearly check that $s \notin L$, for instance:
$$s = xyyz = 0^p0^p1^{2p}0^p = 0^{2p}1^{2p}0^p,\;s \notin L$$

To sum up, $L$ is not regular.

Back to the question, is this a proper way of using the Lemma?

Best Answer

Your basic idea is fine, but some of the details are wrong.

Yes, you can use the string $s=0^p1^{2p}0^p$. You could also use the string $0^p1^{p+1}0^p$: $L$ can also be described as the set of all words $0^k1^\ell0^k$ such that $0<k<\ell$. And when you split $s$ as $s=xyz$ with $|xy|\le p$ and $|y|>0$, it is true that $xy$ must be contained in the first block of zeroes. However, you cannot conclude that $x=\epsilon$ and $y=0^p$. All that you can conclude is that there are non-negative integers $r$ and $s$ such that $x=0^r$, $y=0^s$, $r+s\le p$, and $s\ge 1$. Then $z=0^{p-r-s}1^{2p}0^p$, and

$$xy^kz=0^r0^{ks}0^{p-r-s}1^{2p}0^p=0^{p+(k-1)s}1^{2p}0^p$$

for all $k\ge 0$. This word is in $L$ if and only if the two blocks of zeroes are the same size, i.e, if and only if $p+(k-1)s=p$, which is the case precisely when $k=1$, so pumping the word up (by making $k>1$) or down (by making $k=0$) will give you a word not in $L$. In particular, you can — as you did — take $k=2$ to get

$$xy^2z=0^{p+s}1^{2p}0^p\notin L\,,$$

since $p+s\ne p$, and conclude that $L$ is not regular.

Related Question