Scribd
Upload
186 views3 pages

Closure Properties in Language Theory

This document lists closure properties for common operations on languages in the Chomsky hierarchy and other families of languages. It shows that operations like union and concatenation are closed for regular, context-free, context-sensitive, and recursively enumerable languages, while intersection is only closed for regular and context-sensitive languages. The document also discusses expansions of closure property studies to additional language families and operations.

Uploaded by

Ishan Jawa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
186 views3 pages

Closure Properties in Language Theory

This document lists closure properties for common operations on languages in the Chomsky hierarchy and other families of languages. It shows that operations like union and concatenation are closed for regular, context-free, context-sensitive, and recursively enumerable languages, while intersection is only closed for regular and context-sensitive languages. The document also discusses expansions of closure property studies to additional language families and operations.

Uploaded by

Ishan Jawa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

closure properties on languages∗

CWoo†
2013-03-22 2:59:37

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

∗ hClosurePropertiesOnLanguagesi created: h2013-03-2i by: hCWooi version: h41860i

Privacy setting: h1i hFeaturei h68Q15i h03D55i


† This text is available under the Creative Commons Attribution/Share-Alike License 3.0.

You can reuse this document or portions thereof only if you do so under terms that are
compatible with the CC-BY-SA license.

1
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 homomorphism 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

where the definitions of the cells in the top row are the following language
families:

2
abbreviation name

REG regular
DCFL deterministic context-free
CFL context-free
CSL context-sensitive
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 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 commuta-
tive 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 de-
cidable 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, 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 Au-
tomata, Addison-Wesley, (1969).

You might also like