closure properties on languages

This entry lists some common closure properties on the families of languages corresponding to the Chomsky hierarchy, as well as other related families.

operation	REG	DCFL	CFL	CSL	RC	RE
union	Y	N	Y	Y	Y	Y
intersection	Y	N	N	Y	Y	Y
set difference	Y	N	N	Y	Y	N
complementation	Y	Y	N	Y	Y	N
intersection with a regular language	Y	Y	Y	Y	Y	Y
concatenation	Y	N	Y	Y	Y	Y
Kleene star	Y	N	Y	Y	Y	Y
Kleene plus	Y	N	Y	Y	Y	Y
reversal	Y	Y	Y	Y	Y	Y
$\lambda$-free homomorphism	Y	N	Y	Y	Y	Y
homomorphism	Y	N	Y	N	N	Y
inverse homomorphism	Y	Y	Y	Y	Y	Y
$\lambda$-free substitution	Y	N	Y	Y	Y	Y
substitution	Y	N	Y	N	N	Y
$\lambda$-free GSM mapping	Y	N	Y	Y	Y	Y
GSM mapping	Y	N	Y	N	N	Y
inverse GSM mapping	Y	Y	Y	Y	Y	Y
$k$ limited erasing	Y		Y	Y		Y
rational transduction	Y	N	Y	N	N	Y
right quotient with a regular language	Y	Y	Y	N		Y
left quotient with a regular language	Y	Y	Y	N		Y