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

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.

• 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. – Shaull Jan 19 '14 at 20:07
• Why is its' complement CFL? – TheNotMe Jan 19 '14 at 20:23
• 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\}$. – Yuval Filmus Jan 19 '14 at 20:58
• @Shaull Write as an answer? – Yuval Filmus Jan 19 '14 at 20:59
• @Yuval That is not the complement of $a^nb^n$. $aba$ is not in $a^nb^n$ so it must be in its complement. – G. Bach Jan 19 '14 at 21:45

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?

• Much thanks. And btw, we have not learned DCFL's. – TheNotMe Jan 20 '14 at 7:24