Is there an unambiguous CFL whose complement is not context-free?

Question

I'm doing a little bit of research about context-free languages. A question that's popped up is whether or not there exists an unambiguous context-free language whose complement is not a context-free language.

I know that the complement of a context-free language in general is not necessarily context-free. For example, the language $\{a^m b^n c^p \mid m \ne n \text{ or } n \ne p\}$ is context-free, but its complement, $\{a^m b^n c^p \mid m = n = p\} \cup \overline{a^* b^* c^*}$, is not. I don't see any reason why the complement of an unambiguous context-free language would have to be context-free.

On the other hand, if I understand correctly, the complement of a deterministic context-free language must be a deterministic context-free language; you can get from one automaton to the other just by swapping its accept and reject states. So if there is an unambiguous CFL whose complement is not CF, then it must be non-deterministic.

The most straightforward example of an unambiguous non-deterministic CFL seems to be the language of palindromes of even length, as given by Wikipedia. But the complement of this language seems to be unambiguous as well, having the following grammar:

$$\begin{align*}S &\to T \mid O\\ T &\to aTa \mid bTb \mid U\\ U &\to aVb \mid bVa\\ V &\to aVa \mid aVb \mid bVa \mid bVb \mid \epsilon\\ O &\to aV \mid bV\end{align*}$$

Further thoughts

I came up with another unambiguous CFL whose complement didn't seem like it would be context-free. Upon further reflection, I realized that the language was context-free after all.

Consider the language $D$ defined by $S \to 0S1S \mid \epsilon$ (the language of strings of correctly matched parentheses), and the language $E$ of non-empty even-length palindromes. Both $D$ and $E$ are unambiguous CFGs, and they are disjoint, so $D \cup E$ is also an unambiguous CFG. My reasoning at this point was that a push-down automaton would be unable to recognize $\overline{D} \cap \overline{E}$, because it would have to keep track of two stacks' worth of information.

I then realized that it is indeed possible to create a nondeterministic PDA recognizing this language. Every string in $D$ begins and ends with a different symbol, and every string in $E$ begins and ends with the same symbol. Therefore, the automaton can nondeterministically choose between the following:

• Accept if the string begins and ends with a different symbol, but isn't in $D$; reject otherwise.
• Accept if the string begins and ends with the same symbol, but isn't in $E$; reject otherwise.

Answer 1

Yes, and the first published example is, in a 4-letter alphabet $\{a,b,c,d\}$, the set of all words $a^pb^qc^rd^s$ such that either $$ (10p<q<12p\text{ or } 10q<p<12q)\text{ and } (10r<s<12r \text{ or } 10s<r<12s) $$ or $$ (10q<r<12q \text{ and } 6p<s<8p). $$ Hibbard, T. N.; Ullian, J., The independence of inherent ambiguity from complementedness among context-free languages, J. Assoc. Comput. Mach. 13, 588-593 (1966). ZBL0154.25802.

Abstract:

Call a (context-free) language unambiguous if it is not inherently ambiguous. In the absence of evidence to the contrary, the suspicion has arisen that the unambiguous languages might be precisely those languages with context-free complements. The two theorems presented in this paper lay the suspicion to rest by providing (1) an inherently ambiguous language with context-free complement and (2) an unambiguous language without context-free complement. This establishes the independence of inherent ambiguity from complementedness among the context-free languages.