Search code examples
complexity-theorycontext-free-grammarformal-languagescontext-free-language

Is the complement of any context free language context free?


I read multiple answers that state if a language is not context free, then its complement is context free (correct me if I am wrong). Is this true for the opposite? the complement of a context free language is context free?


Solution

  • Neither statement is true. The complement of a context-free language can be context-free or not; the complement of a non-context free language can be context-free or not.

    Every regular language is context-free. Regular languages are closed under complement, so the complement of a regular language is regular. Consequently, any regular language and its complement are a pair of complementary context-free languages.

    The classic example of a non-context-free language whose complement is context-free is {ww|w∈{0,1}*}. (The proof that its complement is context-free is in the answer to this question.)

    For a non-context-free language whose complement is also not context-free, a simple example is the language whose valid strings are all pairs {(i, x) i halts on input x} (where i is the description of a Turing machine). That language is not context-free, but it is recursively enumerable. Its complement is not even recursively-enumerable. (See Wikipedia)