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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

2
This is essentially an exact duplicate of mathoverflow.net/questions/51657/… which has an answer. – Benjamin Steinberg Feb 21 2012 at 22:27

1
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 2012 at 22:50

1
Ok no longer a duplicate. – Benjamin Steinberg Feb 21 2012 at 22:53

1
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 2012 at 1:55

1
@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 2012 at 21:57
show 1 more comment

## 2 Answers

It seems that the answer to your question is no. See here.

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

Your question is a bit unclear, and when we clarify it, it becomes true.

If by "deterministic context-free grammar" you mean, as usual, an LR(k) grammar for some k, then Knuth proved in his seminal paper ("On the translation of languages from left to right", 1965) that the languages defined are the same as those defined by deterministic PDAs. These are the DFCLs, and the DFCLs are closed under complement. So both your L and L' are DFCLs and hence CFLs, and your last premise is redundant.

Your question really comes down to: are the DFCL's closed under complement -- and they are.

-

2
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 2012 at 16:55
Ah, perhaps. But if so, that's quite a bit more than a typo. He'd simply say "If L is a CFL and L' its complement is also a CFL..." Also, if the question is as you say, then it ~is~ a duplicate of the referenced question, and the answer is "no". Perhaps Nick needs to chime in here. – David Lewis Feb 22 2012 at 17:53
Oh, he accepted that answer -- I guess you are right. – David Lewis Feb 22 2012 at 17:54
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 8, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9420586228370667, "perplexity_flag": "middle"}