9
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.