So I asked a similar question on MathOverflow, but I now realize I asked the wrong question and asked it in the wrong place.

Anyway, I'm searching for a class of languages containing the boolean closure of CFLs that has a 'pumping-type' condition on it. What I've found so far are:

  • MCFGs (multiple context-free languages), which have a nice pumping lemma and contain CFLs (though it's not obvious if they contain the boolean closure of CFLs, since they're not boolean-closed themselves),
  • ET0L languages (which contain CFLs, have a 'pumping-type' lemma, and are (full) AFLs themselves--but I don't think they necessarily contain the boolean closure of CFLs),
  • Mildly CSLs (which apparently have pumping-type lemmas?),
  • Indexed languages (which have a 'shrinking' lemma), etc.

Now, I'm certainly no specialist in formal language theory, so I don't know too much about these classes. Anyway, does such a class exist, and, if so, where can I find papers/etc. on it?


1 Answer 1


This is not an answer to your question per se, but might explain why finding sensible classes of languages more or less fitting your requirements will be hard: recall that the emptiness of intersection of two context-free languages is undecidable, thus the full boolean closure of CFLs is not a very interesting class... (In fact, any R.E. language $L$ can be expressed as $h(L_1\cap L_2)$ for $L_1$ and $L_2$ deterministic context-free and $h$ an homomorphism.)

More in the scope of your question, you can look at Alexander Okhotin's work on conjunctive and boolean grammars, but I don't recall any pumping results.

  • $\begingroup$ You're right--good point. I don't think Okhotin's boolean grammars have any pumping-type results, so ah well! I'll wait a bit more to see if anyone comes along with any magic, but I've taken a different route in my attack anyway. $\endgroup$
    – alpoge
    Commented Jan 11, 2011 at 17:45
  • $\begingroup$ The link to Alexander Okhotin doesn't work now - the new website seems to be here: users.math-cs.spbu.ru/~okhotin $\endgroup$
    – Martin
    Commented Aug 12, 2022 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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