# Are context-free languages with context-free complements necessarily deterministic context-free?

Let $L \subseteq A^\star$ be a formal language over $A$ generated by a context-free grammar, and $L' = A^\star - L$ be the relative complement in $A^\star$.

If $L$ and $L'$ are both context-free, are they necessarily deterministic context-free?

• This is essentially an exact duplicate of mathoverflow.net/questions/51657/… which has an answer. – Benjamin Steinberg Feb 21 '12 at 22:27
• Perhaps you missed my last edit - I removed that part of the question. To clarify, my original question contained the above, as well as a "dual" question concerning the closure of the set of context-free languages w.r.t. finitary Boolean operations. In this question, I'm not looking for the closure of the class of context-free languages with respect to complements, but merely to know if the proper sub-class of CF languages which have CF complements is in fact the class DCF of deterministic CF languages. – Nick Loughlin Feb 21 '12 at 22:50
• Ok no longer a duplicate. – Benjamin Steinberg Feb 21 '12 at 22:53
• In other words, you are asking if $CFL \cap coCFL \subseteq DCFL$ or not. Interesting question. Couldn't find the answer in Hopcroft and Ullman. – Kaveh Feb 22 '12 at 1:55
• @Nick, I rewrote the question to match your comment above as djlewis2 makes a good point. Please re-edit if this was not your intent. – Benjamin Steinberg Feb 22 '12 at 21:57

• You are right, but it seems from the discussion that the OP didn’t actually intend to demand $L$ to be DCFL a priori, it may be a typo. – Emil Jeřábek Feb 22 '12 at 16:55