1
$\begingroup$

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.

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

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

$\endgroup$
2
  • $\begingroup$ thank you, but I thought CFL is not closed under intersection? $\endgroup$
    – Mark Chen
    Apr 2 at 13:06
  • 3
    $\begingroup$ The context-free languages are closed under intersection with regular languages. $\endgroup$ Apr 2 at 13:07

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.