# Prove or disprove {wtw^R | |w| = |t|} is context free

The language $$S_c$$ defined as: $$S_c = \{wtw^R \mid w,t \in \{0,1\}^\star \text{ and } \lvert w \rvert = \lvert t \rvert \}$$

It looks like the language can be "pumped" by context free pumping lemma, but the pumping lemma doesn't prove the language is context free. So I'm thinking of building a PDA that recognizes it. But I'm stuck on constructing the PDA, my initial thought is using nondeterminism to guess the string $$w$$ and $$t$$, then compare the values after $$t$$ which is string $$w^R$$. But still hard for me to come up a whole construction at this moment, any suggestions?

• Consider disproving. – André Souza Lemos Feb 18 at 0:29
• Suppose you have a word $wtw^R$ in which $|t|=|w|=|w^R|>p$. The pumped substring cannot span the three parts of the word, since its length is at most $p$. Now what? – rici Feb 18 at 1:32
• Thanks for all helping me with this question, I just realized I can using pumping lemma to disprove it. Thank you. – hh vh Feb 18 at 1:59
• @hhvh So, I suggest you answer your own question. – Hendrik Jan Feb 18 at 12:34

Suppose $$S_c$$ is context free. Then let $$p$$ be the pumping length and choose $$s = 0^{2p}0^p1^p0^{2p}$$ in $$S_c$$ will satisfied the pumping lemma. Thus, we can break $$s$$ in to $$uvxyz$$, with $$|vxy| \leq p$$ and $$|vy| \geq 1$$. And for any $$i$$, $$uv^ixy^iz$$ is a string in $$S_c$$. Now, we have three cases for above conditions:
1. $$vy$$ contains all 0s and these 0s can chosen from either the begin $$0^{2p}$$ of $$s$$, middle $$0^p1^p$$ of $$s$$ and the last $$0^{2p}$$ of $$s$$. Now, by pumping lemma, since $$uv^ixy^iz \in S_c$$, for any $$i$$. We choose $$i$$ = 2, so we have $$s'$$ = $$uv^2xy^2z$$ = $$uvvxyyz$$. Clearly, since $$vy$$ contains all 0s, and regardless which part of $$s$$ are chosen from, this string is the form of $$wtw^R$$ such that $$|w|$$ = $$|t|$$ = $$w'$$ with either $$w$$ is all 0's and $$w'$$ is not all 0s or vice verse. This implies that $$w' \neq w^R$$ or $$w' \neq w$$.
2.$$vy$$ doesn't contain any 0s in last $$0^{2p}$$ of $$s$$(We choose in the last part of $$s$$, but it's essentially the same by choosing first or middle of $$s$$). Similarly, either the length of $$uv^2xy^2z$$ is not multiply of 3(since pumping will increase the number of 1's), or this string is the form of $$wtw'$$ such that $$|w|$$ = $$|t|$$ = $$|w'|$$ with $$w$$ is form of all 0s but $$w'$$ contains some 1s. Thus $$w' \neq w^R$$.
1. $$vy$$ contains some 0s and some 1s in last $$0^{2p}$$ of $$s$$. From pumping lemma, since $$vxy \leq q$$, then $$vxy$$ must be sub-string of $$0^p1^p$$. Then, by pumping the string $$s' = uv^ixy^iz$$ for any $$i$$, the length is string is not multiply of 3 since pumping increase number of 0s or 1s, or the string is the form of $$wtw'$$ such that $$|w|$$ = $$|t|$$ = $$|w'|$$ with $$w$$ is form of all 0s but $$w'$$ is not all 0s.
Thus, we can conclude that above's three cases all reach contradiction to context free pumping lemma and hence $$S_c$$ is not context free.