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 2


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.

  • $\begingroup$ I am afraid this does not answer the question. $\endgroup$
    – J.-E. Pin
    Commented Apr 1, 2016 at 16:28
  • $\begingroup$ 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 $\endgroup$
    – Karo
    Commented Apr 1, 2016 at 16:30
  • 3
    $\begingroup$ 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?" $\endgroup$
    – J.-E. Pin
    Commented Apr 1, 2016 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.