I know that the context-free language is not closed under the complement , and the result could be context-free language or non-context free language but my question is :

is it possible of the complement of context-free language = regular language ?

  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Apr 12 '19 at 6:24

Since regular languages are all context-free and REG is closed against complement, every regular language is such an example.

As for non-regular context-free languages, the same closure property with a sprinkle of proof by contradiction easily shows that none of them can have a regular complement.

| 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.