It is known, that there exist context free languages with non context free complement (for example $A^* \setminus A^*A^*$ for any finite alphabet $A^*$). It is also known, that there are recursively enumerable languages with non recursively enumerable complement (for example, the language corresponding to the halting problem, or the word problems of some certain groups). However, all context free languages in those examples of the first type have recursively enumerable complements and all recursively enumerable languages in those examples of the second type are not context free.

My question is:

Does there exist a context free formal language, the complement to which is not recursively enumerable?


Every context-free language is recursive, so its complement is also recursive and therefore recursively enumerable.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.