2
$\begingroup$

I'm trying to show that $L=\left\{w^rww^r:w \in \{0,1\}^*\right\}$ is not context free using the pumping lemma.

I thought picking the string, $0^p0^p0^p$, would be a good candidate for this, but someone told me I might want to consider another string. Why is this? Any way in which I divide the string and then pump the string results in the balances between the $w^r$on either side of the string being thrown off, no?

$\endgroup$
2
$\begingroup$

For $p>0$, you can always split $0^{3p}$ into $uvxyz$ such that $u=x=\varepsilon$, $v=0$, $y=0^2$, and $z=0^{3p-3}$. Such a split clearly satisfies $|vxy|\leq p$, $|vy|\geq1$. Finally, for all $n\geq0$, $uv^nxy^nz=0^{3(p-1+n)}$, which is in $L$, since $0^{3m}\in L$ for all $m$.

Since you want to show, that for an arbitrary split satisfying the length conditions, there is some $n$ for which $uv^nxy^nz\notin L$, the choice of $0^{3p}$ is unfortunate.

$\endgroup$
1
$\begingroup$

The string $0^{3p}$ can always be pumped so that it stays in $L$. Recall what the pumping lemma says: there exists a $p \in \mathbb{N}$ such that any $w \in L$ of size at least $p$ can be written as $w=uvxyz$ such that $|vxy| \leq p$, $|vy| \geq 1$ and $uv^ixy^iz \in L$ for all $i \in \mathbb{N}$. In your case, we can choose $u = x = y = \epsilon$ and $v=0^3$, and then $uv^ixy^iz = 0^{3(p-1+i)} \in L$, and so no contradiction can be obtained using the word $0^{3p}$.

In order to prove using the pumping lemma that $L$ is not regular, you need to come up with a word $w$ so that for every possible decomposition $w = uvxyz$ such that $|vxy| \leq p$ and $|vy| \geq 1$, there exists some $i \in \mathbb{N}$ such that $uv^ixy^i z \notin L$. For your word $w$ this is not the case, since the decomposition indicated above is "bad". While you are free to choose $w$, you are not free to choose the decomposition $w = uvxyz$; your argument should work for all possible decompositions.

In fact, the word $w = 0^{3p}$ doesn't even help in showing that $L$ is not regular; we can choose the decomposition $w = xyz$ with $x = \epsilon$ and $y = 0^3$, and then $xy^i z = 0^{3(p-1+i)} \in L$.

The root cause of all these problems is that $L \cap 0^* = \{0^n : 3|n\}$, which is regular. So you have to look at a word which contains both $0$s and $1$s.

$\endgroup$

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.