Are context-free languages with context-free complements necessarily deterministic context-free? - MathOverflow 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 Are context-free languages with context-free complements necessarily deterministic context-free? 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 Answer by Benjamin Steinberg for Are context-free languages with context-free complements necessarily deterministic context-free? 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 Answer by David Lewis for Are context-free languages with context-free complements necessarily deterministic context-free? 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>