most recent 30 from http://mathoverflow.net 2013-05-24T10:13:47Z http://mathoverflow.net/feeds/question/89142 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/89142/are-context-free-languages-with-context-free-complements-necessarily-deterministi Nick Loughlin 2012-02-21T21:46:23Z 2012-02-22T21:55:46Z

<p>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$.</p> <p>If $L$ and $L'$ are both context-free, are they necessarily deterministic context-free?</p>

http://mathoverflow.net/questions/89142/are-context-free-languages-with-context-free-complements-necessarily-deterministi/89197#89197 Benjamin Steinberg 2012-02-22T14:35:23Z 2012-02-22T14:35:23Z

<p>It seems that the answer to your question is no. See <a href="http://cstheory.stackexchange.com/questions/4263/the-class-cfl-cap-co-cfl" rel="nofollow">here</a>. </p>

http://mathoverflow.net/questions/89142/are-context-free-languages-with-context-free-complements-necessarily-deterministi/89212#89212 David Lewis 2012-02-22T16:49:03Z 2012-02-22T16:49:03Z

<p>Your question is a bit unclear, and when we clarify it, it becomes true. </p> <p>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. </p> <p>Your question really comes down to: are the DFCL's closed under complement -- and they are.</p>