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

Remarks. Based on the table above, studies in closure properties have been expanded in other directions, such as

• closure properties of the above operations on more families of languages, such as linear languages, indexed languages, and mildly context-sensitive languages
• given that an arbitrary family of languages is closed under a subset of operations above, what more can one say about the family? what other closure properties can be deduced? This is known as AFL (abstract family of languages) theory.
• closure properties of yet more operations on languages, such as commutative closures, shuffle closures, insertion closures, deletion closures, subword extensions, prefix extensions, and suffix extensions.
• knowing that a closure property of an operation is not satisfied for a given language family, study the closure of the property on the family. For example, what is the Boolean closure of context-free languages?
• knowning the a closure property of an operation is not satisfied for a given language family, study whether it is decidable that taking the operation on language(s) leads to a language in the family. For example, is it decidable that the intersection of two context-free languages is context-free? Furthermore, if the problem is decidable, what is its complexity?

Bibliography

1

A. P. Parkes, Introduction to Languages, Machines, and Logic, Springer (2002).

2

A. Salomaa, Formal Languages, Academic Press, New York (1973).

3

J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, (1969).