3
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – alpoge
    Commented Jan 10, 2011 at 16:39

3 Answers 3

Reset to default
5
$\begingroup$

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

Alexander Okhotin (Wayback Machine) 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) (Wayback Machine). The last inclusion is also strict: there are context-sensitive languages which cannot be specified by a boolean grammar.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – alpoge
    Commented Jan 10, 2011 at 19:28
  • $\begingroup$ I have added Wayback Machine links for both links to the Alexander Okhotin's website. It seems that he now has a website at users.math-cs.spbu.ru/~okhotin - but this new website doesn't have a working link to the PDF-file which is relevant here. $\endgroup$
    – Martin Sleziak
    Commented Aug 12, 2022 at 12:10
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – alpoge
    Commented Jan 10, 2011 at 16:29
1
$\begingroup$

This looks interesting as well.

Kutrib, Martin; Malcher, Andreas; Wotschke, Detlef, The Boolean closure of linear context-free languages, Calude, Cristian S. (ed.) et al., Developments in language theory. 8th international conference, DLT 2004, Auckland, New Zealand, December 13–17, 2004. Proceedings. Berlin: Springer (ISBN 3-540-24014-4/pbk). Lecture Notes in Computer Science 3340, 284-295 (2004). ZBL1117.68408, MR2152151.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

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