# Pumping lemma for an involved non context free language

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.

• $\{ww^{R}|w\in\{0,1\}^+\}$ is a context-free language. Commented Apr 2, 2021 at 12:36
• Sorry my bad, I meant ${ww}$ instead of $ww^R$ Commented Apr 2, 2021 at 12:37

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