# 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. Feb 18, 2020 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, 2020 at 1:32
• Thanks for all helping me with this question, I just realized I can using pumping lemma to disprove it. Thank you. Feb 18, 2020 at 1:59
• @hhvh So, I suggest you answer your own question. Feb 18, 2020 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$$ that satisfies the pumping lemma. Thus, we can break $$s$$ into $$uvxyz$$, with $$|vxy| \leq p$$ and $$|vy| \geq 1$$. And for all $$i$$, $$uv^ixy^iz$$ is a string in $$S_c$$.
1. $$vy$$ contains all 0s and these 0s can be chosen from either the beginning $$0^{2p}$$ of $$s$$, middle $$0^p1^p$$ of $$s$$ or the last $$0^{2p}$$ of $$s$$. Now, by pumping lemma, since $$uv^ixy^iz \in S_c$$, for all $$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 part of $$s$$). Similarly, either the length of $$uv^2xy^2z$$ is not multiple 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$$ consists all 0s but $$w'$$ contains some 1s. Thus $$w' \neq w^R$$.
3. $$vy$$ contains some 0s and some 1s in last $$0^{2p}$$ of $$s$$. From pumping lemma, since $$vxy \leq q$$, $$vxy$$ must be sub-string of $$0^p1^p$$. Then, by pumping the string $$s' = uv^ixy^iz$$ for all $$i$$, the length is string is not multiple of 3 since pumping increases number of 0s or 1s, or the string is in the form of $$wtw'$$ such that $$|w|$$ $$=$$ $$|t|$$ $$=$$ $$|w'|$$ with $$w$$ is all 0s but $$w'$$ is not all 0s.
Thus, we can conclude that all three cases above reach contradiction and hence $$S_c$$ is not context free.