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?

  • 2
    $\begingroup$ Consider disproving. $\endgroup$ Feb 18, 2020 at 0:29
  • 2
    $\begingroup$ 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? $\endgroup$
    – rici
    Feb 18, 2020 at 1:32
  • $\begingroup$ Thanks for all helping me with this question, I just realized I can using pumping lemma to disprove it. Thank you. $\endgroup$
    – hh vh
    Feb 18, 2020 at 1:59
  • 2
    $\begingroup$ @hhvh So, I suggest you answer your own question. $\endgroup$ Feb 18, 2020 at 12:34

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.