[Solved]: If $L$ is CFL and $\overline{L}$ is CFL, then is L regular?

Problem Detail: 

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.

Asked By : TheNotMe

Answered By : sdcvvc

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?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19834

3.2K people like this

 Download Related Notes/Documents