I've seen in previous exams that professors marked the theory as correct:

If $L$ is CFL and $\overline{L}$ is CFL, then L is regular.

I just don't see how this would work. How would we prove such a thing? I also can't come up with contradicting languages.

  • 3
    $\begingroup$ The theorem is incorrect. The language of words with an equal number of $a$'s and $b$'s, and its complement, are both in CFL but are not regular. $\endgroup$
    – Shaull
    Jan 19, 2014 at 20:07
  • $\begingroup$ Why is its' complement CFL? $\endgroup$
    – TheNotMe
    Jan 19, 2014 at 20:23
  • $\begingroup$ Since $\{a^n b^m : n \neq m\} = \{a^n b^n b^t : t \geq 1 \} \cup \{a^t a^n b^n : t \geq 1\}$. $\endgroup$ Jan 19, 2014 at 20:58
  • $\begingroup$ @Shaull Write as an answer? $\endgroup$ Jan 19, 2014 at 20:59
  • 2
    $\begingroup$ @Yuval That is not the complement of $a^nb^n$. $aba$ is not in $a^nb^n$ so it must be in its complement. $\endgroup$
    – G. Bach
    Jan 19, 2014 at 21:45

1 Answer 1


As Shaull noted in the comments, $\{a^n b^n\}$ works. The language is trivially context-free but not regular, so I'll show the complement is context-free. A word which is not of the form $a^n b^n$ is either $a^n b^m$ where $n\neq m$, or not of the form $a^n b^m$ at all. So

$(a+b)^{\ast}-{a^n b^n}=\{a^i b^j: i \neq j\} \cup ((a+b)^{\ast}-a^{\ast} b^{\ast})$

which is a sum of context-free language $\{a^i b^j: i \neq j\}$ and the complement of $a^{\ast} b^{\ast}$ which is a regular language.

Another way to see it is that $\{a^n b^n\}$ is a deterministic context-free language, which is a class closed under complement. In other words any nonregular DCFL is a counterexample to the question.

I'll leave the following question to the reader:

Suppose $L$ and $\overline L$ are CFLs, is $L$ a DCFL?

  • $\begingroup$ Much thanks. And btw, we have not learned DCFL's. $\endgroup$
    – TheNotMe
    Jan 20, 2014 at 7:24

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.