Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider two context-free languages $L_1, L_2$. Of course, $L_1 - L_2, L_1\cap L_2, \bar{L}_1$, etc. are not necessarily context-free, but they are context-sensitive (the second is easy, the other two I think follow from Immerman-Szelepcsenyi (if I spelled that right)). However, there's no nice structure to context-sensitive languages (e.g., pumping/Ogden's lemmas), so I was wondering if the inclusion is any better--is the 'closure' of CFLs under the standard operations (well, only $\cap$ and complementation) a proper subset of CSLs, and if so, does it have any natural description?

Thanks much.

share|improve this question
The title makes this sort of look like a question about introductory CS... By 'closure' I mean the smallest set containing the set of CFLs that is closed under those operations. –  alpoge Jan 10 '11 at 16:39

3 Answers 3

up vote 3 down vote accepted

Grammars involving the usual context-free operations plus intersection are called conjunctive grammars. Adding negation (in addition to intersection) gives boolean grammars.

Alexander Okhotin has done quite a bit of recent work on the closure properties of the languages (sets of strings) specified by these sorts of grammars. He also has a paper showing how to parse these languages using a variant on the Lang-Tomita GLR algorithm.

As you note, CFLs are strictly included in conjunctive grammars. Surprisingly, it appears that the strictness of the inclusion relationship between conjunctive and boolean grammars is still an open problem (#6). The last inclusion is also strict: there are context-sensitive languages which cannot be specified by a boolean grammar.

share|improve this answer
This looks right. Thanks! –  alpoge Jan 10 '11 at 18:35
It seems conjunctive grammars also strictly contain the set of $2$-intersection languages with complementation (or whatever one might call them), since in the unary case the set of conjunctive languages contains nonregular languages (which are obviously not in the previous set). Though conjunctive/boolean grammars do indeed answer the question. Thanks again! –  alpoge Jan 10 '11 at 19:28

Would An infinite hierarchy of intersections of context-free languages (Liu Weiner 1973) answer your question? They prove that the intersection of $k$ CFL forms a class strictly contained in the intersection of $k +1$ CFL.

share|improve this answer
Hm. I suppose that probably shows that the 'closure' I'm talking about is pretty complicated at least. What I really want to know is about $2$-intersection languages--well, specifically, $2$-intersection languages 'adjoined' with the co-CFL languages, so to speak. –  alpoge Jan 10 '11 at 16:29

This looks interesting as well.

share|improve this answer
Have you also seen "The Boolean closures of the deterministic and nondeterministic context-free languages" (Wotschke 1973, springerlink.com/content/y633h2x084w2v876)? –  Tara Brough Apr 4 '11 at 12:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.