2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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