3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.