Pumping lemma for an involved non context free language

Question

Hi I'm trying to show $C=\{wzzw^R|w,z\in\{0,1\}^+\}$ is not a context-free language.( I have this believe because $C=\{ww|w\in\{0,1\}^+\}$ is not a context free language.) I'm really struggling to come up with a string that captures the essence of irregularity of this language: I tried strings like $s=1^p0^p1^p0^p1^p1^p$ but there are too many cases to deal with and most of the examples I saw only use 1 or 2 cases, so I believe the direction I'm going is wrong. Can you provide a hint on which string to pick as the 'pumping string'? Thank you.

Answer 1

Suppose that $C$ were context-free. Then the following language would also be context-free: $$ C' = C \cap 0(100+110)^+0. $$ What does $C'$ look like? Suppose that $x = wzzw^R$ belongs to $0(100+110)^+0$, where $z,w \neq \epsilon$. Note that the first two symbols of $x$ are $01$, and last two are $00$. This shows that $w = 0$, and so $zz$ belongs to $(100+110)^+$. Thus $|zz| = 3m$ for some $m \geq 1$. Since $|zz|$ is even, $m = 2k$, and so $|z| = 3m/2 = 3k$. Therefore $z$ belongs to $(100+110)^+$, and we conclude that $$ C' = \{ 0 zz 0 : z \in (100+110)^+ \}. $$ If $C'$ were context-free, then so would be the language $$ 0^{-1} C' 0^{-1} = \{ zz : z \in (100+110)^+ \}, $$ obtained by taking left and right quotients with $\{0\}$. Finally, if we define a homomorphism $h\colon \{a,b\} \to \{0,1\}^*$ by $h(a) = 100$ and $h(b) = 110$ then the following language would also be context-free: $$ h^{-1}(0^{-1} C' 0^{-1}) = \{ zz : z \in (a+b)^* \}. $$ Since this language is well-known not to be context-free, we conclude that so is $C$.