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

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?

## 1 Answer

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.