New answers tagged


The complement of a context-free language $L$ is not necessarily context-free, but it is the difference between two context-free languages ($\Sigma^* - L$). (Here $\Sigma$ is the alphabet of $L$.) See, for example, Is the complement of { ww | ... } context-free? for an example of a context-free language whose complement is not context-free.


If I understand your argument correctly, you are reducing languages in the wrong direction. If $L$ is not context-free, then $K$ is not context-free. Is equivalent to If $K$ is context-free, then $L$ is context-free. We have to reverse the construction, as we are using the closure properties of the context-free languages. In do not know of any useful ...


Your reasoning is essentially correct. Assuming your TMs are deciders (i.e., they must also properly reject their inputs), you don't even need an extra step in your algorithm; you can just swap the accept and reject states of your TM (just like you do with DFAs!). In case your TMs are only defined as acceptors (i.e., a word not in the language will not ...


Every deterministic complexity class (DSPACE(f(n)), DTIME(f(n)) for all f(n)) is closed under complement,[8] because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse ...

Top 50 recent answers are included