A note on algebras of languages

We study the Boolean algebras R, CS, D of regular languages, context-sensitive languages and decidable languages, respectively, over any alphabet. It is well known that R ⊂ CS ⊂ D, with proper inclusions. After observing that these Boolean algebras are all isomorphic, we study some immunity properties: for instance we prove that for every coinfinite decidable language L there exists a decidable language L′ such that L ⊆ L′ , L′ −L is infinite, and there is no context-sensitive language L′′ , with L′′ ⊆ L′ unless L′′ − L is finite; similarly, for every coinfinite regular language L there exists a context-sensitive language L′ such that L ⊆ L′ , L′−L is infinite, and there is no regular language L′′ such that L′′ ⊆ L′ , unless L′′−L is finite.