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

Both palindrome and its complement are context-free. This is very interesting. Both are non-deterministic context-free, which in general are not closed under complement. What is it about these two NCFLs that makes complement work?

## 2 Answers

You make the mistake of assuming that

$\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \quad \forall\, x \in X. \lnot P(x)$

while in truth

$\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \quad \exists\, x \in X. \lnot P(x)$.

In your concrete case, "CFL is not closed against complement" means there are counterexample. You'll recall that REG ⊆ CFL and REG is closed against complement, so there are clearly plenty of complement-pairs in CFL.

As for the concrete two languages, the palindromes are generated by the most archetypical context-free grammar,

$\qquad S \to aSa \mid bSb \mid \dots \mid a \mid b \mid \dots \varepsilon$.

The complement is a nice exercise and can be found elsewhere on the site.

when we say that context free language is not closed under complement it means that that there exist some contest free language that its complement is not context free language not for all languages. for example $L = \{w\in\{a,b,c\}^+ : n_a(w) = n_b(w) = n_c(w)\}$ is not context free language while its complement is context free language. you can see other example here.

but when we say context free language is close under union it means for all $L_1$ and $L_2$ that are context free language, $L_1 \cup L_2$ is context free language.

• I am afraid this does not answer the question. – J.-E. Pin Apr 1 '16 at 16:28
• I was thinking that his question is why there is some language that itself and its complement both are CFL while CFL is not close under complementation @J.-E.Pin – Karo Apr 1 '16 at 16:30
• My understanding is rather "What is so specific in the palindrome language that makes this language and its complement context-free without being deterministic context-free?" – J.-E. Pin Apr 1 '16 at 16:36