You are here
Homeclosure properties on languages
Primary tabs
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 
where the definitions of the cells in the top row are the following language families:
abbreviation  name 

REG  regular 
DCFL  deterministic contextfree 
CFL  contextfree 
CSL  contextsensitive 
RC  recursive 
RE  recursively enumerable 
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 contextsensitive 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.

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 contextfree languages is contextfree? Furthermore, if the problem is decidable, what is its complexity?
References
 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, AddisonWesley, (1969).
Mathematics Subject Classification
68Q15 no label found03D55 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections