3
$\begingroup$

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.

$\endgroup$
  • 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 '14 at 20:07
  • $\begingroup$ Why is its' complement CFL? $\endgroup$ – TheNotMe Jan 19 '14 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$ – Yuval Filmus Jan 19 '14 at 20:58
  • $\begingroup$ @Shaull Write as an answer? $\endgroup$ – Yuval Filmus Jan 19 '14 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 '14 at 21:45
10
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.