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?
Why are palindrome and not-palindrome both context-free?
formal languages;context free;closure properties