Is the Complement of the Language $L=\{wxw^r|w \in (a+b)^+, x \in (a+b) \}$ Context free?

Question

I know that the Context-free languages are not closed under compliment.

Given $L=\{wxw^r| w \in(a+b)^+,x \in (a+b)\}$ and this is a Context free language. I think it's compliment will contain words of the form $ww$ which comes under CSL.So, I think this $\lnot L$ must be not context-free.But I've read here

Why are palindrome and not-palindrome both context-free?

that palindromes are closed under complement.

Can someone please guide over this?

Answer 1

Generally speaking, the way to figure out whether a given language is context-free is twofold:

• Try proving that it is not context-free, say using the pumping lemma.
• Try proving that it is context-free, say by constructing a grammar or a PDA.

If any of these methods succeed, you will have found whether the language is context-free.

In your particular case, we can notice that a word $y$ is not in $L$ if one of the following three cases occurs:

• $y$ has even length.
• $y$ has length one.
• $y$ has odd length, and when written as $y = z \sigma w^R$, with $|z| = |w|$, the two words are different.

In the third case, let us suppose that $z_i = \alpha \neq \beta = (w^R)_i$, and put $\ell = |z| = |w|$. Then $y \in \Sigma^{i-1} \alpha \Sigma^{\ell-i} \sigma \Sigma^{\ell-i} \beta \sigma^{i-1}$, and all such words are not in $L$. We conclude that $$ \overline{L} = (\Sigma\Sigma)^* \cup \Sigma \cup \bigcup_{\substack \sigma, \alpha \neq \beta \in \Sigma \\ j,k \geq 0} \Sigma^j \alpha \Sigma^k \sigma \Sigma^k \beta \Sigma^j. $$ It is routine to construct a context-free grammar for the expression on the right, and so $\overline{L}$ is context-free.