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 |
λ-free homomorphism![]() |
Y | N | Y | Y | Y | Y |
homomorphism | Y | N | Y | N | N | Y |
inverse![]() |
Y | Y | Y | Y | Y | Y |
λ-free substitution | Y | N | Y | Y | Y | Y |
substitution | Y | N | Y | N | N | Y |
λ-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 |
wherethedefinitionsofthecellsinthetoprowarethefollowinglanguagefamilies:Unknown node type: spanUnknown node type: br𝐑𝐞𝐦𝐚𝐫𝐤𝐬.Basedonthetableabove,studiesinclosurepropertieshavebeenexpandedinotherdirections,suchas • 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? References 1 A.P.Parkes,IntroductiontoLanguages,Machines,andLogic,Springer(2002). 2 A.Salomaa,FormalLanguages,AcademicPress,NewYork(1973). 3 J.E.Hopcroft,J.D.Ullman,FormalLanguagesandTheirRelationtoAutomata,Addison-Wesley,(1969).Titleclosure properties on languagesCanonical nameClosurePropertiesOnLanguagesDate of creation2013-03-22 18:59:36Last modified on2013-03-22 18:59:36OwnerCWoo (3771)Last modified byCWoo (3771)Numerical id6AuthorCWoo (3771)Entry typeFeatureClassificationmsc 68Q15Classificationmsc 03D55Related topicAbstractFamilyOfLanguages