Language equivalency for modified CFG closed over intersection

Question

Suppose "CFG+" was created, where it is identical to standard context-free grammars in every way, but rather than rules being limited to unions, was also closed over intersections, both between CFGs and between other CFG+'s.

Consider non-context-free language: $$ \{ a^nb^nc^n|n≥0\} $$

With the addition of intersections, consider the following "CFG+": $$ S\rightarrow AB\ \&\ CD $$ $$ A\rightarrow aAb\ |\ \epsilon $$ $$ B\rightarrow cB\ |\ \epsilon $$ $$ C\rightarrow aC\ |\ \epsilon $$ $$ D\rightarrow bDc\ |\ \epsilon $$

As AB covers when #a = #b, and CD when #b = #c, this intersection will match the non-context-free language given above.

It is obvious that context-free languages are a strict subset of the languages described by CFG+. However, how does this compare with other languages? Is this equivalent to a context sensitive grammar? An unrestricted grammar? Is there already a language category I should be recognizing this as?

Answer 1

It looks like by describing your "CFG+" grammar, you have independently reinvented/rediscovered the conjunctive grammar.

Here is more quote from that article on Wikipedia.

The family of conjunctive languages is closed under union, intersection, concatenation and Kleene star, but not under string homomorphism, prefix, suffix, and substring. Closure under complement and under $\epsilon$-free string homomorphism are still open problems.

Since context-sensitive languages are closed under complement, the family of conjunctive languages is a strict subset of the family of context-sensitive languages. In fact, the family of languages generated by boolean grammars, grammars that extends conjunction grammars with negation operations, is also a strict subset of the family of the context-sensitive languages.

---

A related problem is the expressive power of intersections of context-free languages.

An infinite hierarchy of intersections of context-free languages by Liu and Weiner shows that ($d$-1)-intersection closure of context-free languages is strictly contained in the $d$-intersection closure of context-free languages, since the language $\{a_1^{n_1} a_2^{n_2} \cdots a_{d}^{n_{d}} b_1^{n_1} b_2^{n_2} \cdots b_d^{n_d} \mid n_1,n_2,\ldots ,n_d\ge 0\}$ is contained in the latter family of languages but not in the former family of languages for all $d\ge2$.

Answer 2

Every such grammar will describe a context-sensitive language: every context-free language is also context-sensitive, and context-sensitive languages are closed under intersection.

I don't know if this describes a proper subset of the context-sensitive languages, or if every context-sensitive language can be formulated in this way.