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

Question

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?

Answer 1

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$.

We have three cases.

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.