What is the closure of the class of context-free languages under intersection?

119 Views Asked by At

Let $\mathsf{CF}$ be the class of context-free languages. As is well known, $\mathsf{CF}$ is not closed under intersections; the classical counterexample is the intersection of $\{a^mb^mc^n\mid m,n\in\mathbb N\}$ with $\{a^mb^nc^n\mid m,n\in\mathbb N\}$. Can one explicitly describe the closure of $\mathsf{CF}$ under (finite) intersections?

Note that $\mathsf{CF}$ is a subclass of $\mathsf{CS}$, the context-sensitive languages, and that $\mathsf{CS}$ is closed under intersection, so the closure is contained in $\mathsf{CS}$. Then the question boils down to, is every context-sensitive language a finite intersection of context-free languages, or is there a "nice" intermediate class that is closed under intersections?

I find it surprising that the answer to this natural question appears hard to find in the literature.

1

There are 1 best solutions below

0
On

Let $L = \{wcw \mid w \in \{a,b\}^*\}$. It is shown in [1] that the complement of $L$ is context-free and thus $L$ is context-sensitive. However $L$ cannot be expressed as a finite intersection of context-free languages.

It follows that the class $\cap\mathsf{CF}$ of finite intersections of context-free languages is strictly included in the class $\mathsf{CS}$ of context-sensitive languages.

[1] D. Wotschke, The Boolean closures of the deterministic and nondeterministic context-free languages. Dritte Jahrestagung der Gesellschaft für Informatik (Hamburg, 1973), pp. 113--121. Lecture Notes in Comput. Sci., Vol. 1, Springer, Berlin, 1973.