Regular Separability and Intersection Emptiness are Independent Problems

Ramanathan S. Thinniyam, Georg Zetzsche

The problem of \emph{regular separability} asks, given two languages $K$ and $L$, whether there exists a regular language $S$ with $K\subseteq S$ and $S\cap L=\varnothing$. This prob…