Example of context-free but non regular language with context-free complement

1.9k Views Asked by At

As we know context-free languages are not closed under complement. But are there examples of non regular context-free languages which complement is context-free?

We know that regular languages is smallest class containing finite languages closed under sum, complement, concatenation and Kleene star. Context-free languages are similar but are not closed under complement. Does it mean that there are no such language?

2

There are 2 best solutions below

0
On BEST ANSWER

Deterministic context-free languages are closed under complement.

0
On

An example: $\{a^n b^n: n \geq 0\}$; you can check that the complement is context-free by writing it as an appropriate union.