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$ – André Souza Lemos Feb 18 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 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 at 1:59
  • 2
    $\begingroup$ @hhvh So, I suggest you answer your own question. $\endgroup$ – 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.

| cite | improve this answer | |

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.