1
$\begingroup$

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?

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Deterministic context-free languages are closed under complement.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .