# What is the closure of context-free languages under finite intersections?

Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive.

So this leads to the question: what is the closure of context-free languages under finite intersections? Does this class of formal languages have a name? Do we get all context-sensitive languages this way?

The intersections of context-free languages will never reach the full family of context-sensitive languages.

The class of languages expressible as the intersection of $$k$$ context-free languages is shown to be properly contained within the class of languages expressible as the intersection of $$k + 1$$ context-free languages. Hence an infinite hierarchy of classes of languages is exhibited between the class of context-sensitive languages and the class of context-free languages.

Quoted from: An infinite hierarchy of intersections of context-free languages. Leonard Y. Liu & Peter Weiner Mathematical Systems Theory 7 (1973) 185–192. https://doi.org/10.1007/BF01762237 (paywall)

An explicit example is also given, with a reference to the PhD thesis of the first author.

not every context-sensitive language is expressible as an intersection of a finite number of context-free languages, e.g., $$L = \{ a^{2^n} \mid n \in \mathbb N \}$$.

Note however, that context-free languages over a one letter alphabet are in fact regular. That means that if a finite number of CF languages intersects to a language in $$\{a\}^*$$, then we can as well assume each of these languages to be within $$\{a\}^*$$. This implies we intersect a finite number of regular languages, which is regular again.

Intersections (and more generally, Boolean combinations) of context-free languages are included in the class LOGCFL, which is a quite weak subclass of P (on a low level of the NC hierarchy). Thus, it is very far from the class of all context-sensitive languages. In particular, $$\mathrm{LOGCFL\subseteq DSPACE}((\log n)^2)$$, while $$\mathrm{CSL=NSPACE}(n)$$; the space hierarchy theorem ensures that these classes are different, and that there are many intermediate levels of conplexity in between them.