Determine if complement of non-regular language is context-free

Question

I'm trying to understand if the complement of non-regular language is context-free.

for example: $L=\{ 0^n 1^n │ n\ge0 \}$,

I need to prove that the complement of $L$ is regular so $L'$ is context-free.

can I see an example?

Answer 1

You will struggle to prove the complement of $L$ is regular, because it isn't. Recall regular languages are closed under complementation, but $L$ is famously not regular.

That said, you can still show $L^c$ is context free. The trick is to break it up into multiple pieces, and remember that context free languages are closed under union. As a hint, $L^c$ consists of

• all strings of the form $0^i 1^j$ with $i \neq j$
• all strings which aren't of the form $0^i 1^j$ at all.

Can you show that each of these is context free? If you're still struggling, see if you can break them down into a union of even simpler languages.

Good luck!

---

I hope this helps ^_^