Abstract family of languages
Encyclopedia
In computer science
, in particular in the field of formal language
theory,
the term abstract family of languages refers to an abstract mathematical notion generalizing characteristics common to the regular language
s, the context-free language
s and the recursively enumerable language
s, and other families of formal languages studied in the scientific literature.
is a set
for which there exists a finite set of abstract symbols 
such that 
, where * is the Kleene star
operation.
A family of languages is an ordered pair
, where
A trio is a family of languages closed
under e-free homomorphism, inverse homomorphism
, and intersection with regular language
.
A full trio, also called a cone
, is a trio closed under arbitrary homomorphism.
A (full) semi-AFL is a (full) trio closed under union
.
A (full) AFL is a (full) semi-AFL closed under concatenation
and the Kleene plus.
Within the Chomsky hierarchy
, the regular language
s, the context-free language
s, and the recursively enumerable language
s are all full AFLs. However, the context sensitive languages
and the recursive language
s are AFLs, but not full AFLs because they are not closed under arbitrary homomorphisms.
The family of regular languages are contained within any cone (full trio). Other categories of abstract families are identifiable by closure under other operations such as shuffle, reversal, or substitution.
of the University of Southern California
and Sheila Greibach
of Harvard University
presented the first AFL theory paper at the IEEE Eighth Annual Symposium on Switching and Automata Theory in 1967.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, in particular in the field of formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
theory,
the term abstract family of languages refers to an abstract mathematical notion generalizing characteristics common to the regular language
Regular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
s, the context-free language
Context-free language
In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
s and the recursively enumerable language
Recursively enumerable language
In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-acceptable. It is known as a type-0 language in the Chomsky hierarchy of formal languages...
s, and other families of formal languages studied in the scientific literature.
Formal definitions
A formal languageFormal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
is a set
for which there exists a finite set of abstract symbols such that , where * is the Kleene starKleene star
In mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*...
operation.
A family of languages is an ordered pair
, where
-
is an infinite set of symbols; -
is a set of formal languages; - For each
in 
there exists a finite subset 
⊂ 
such that 
⊆ 
; and -
≠ Ø for some 
in 
.
A trio is a family of languages closed
Closure (mathematics)
In mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...
under e-free homomorphism, inverse homomorphism
Homomorphism
In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...
, and intersection with regular language
Regular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
.
A full trio, also called a cone
Cone (formal languages)
In formal language theory, a cone is a set of formal languages that has some desirable closure properties enjoyed by some well-known sets of languages, in particular by the families of regular languages, context-free languages and the recursive languages...
, is a trio closed under arbitrary homomorphism.
A (full) semi-AFL is a (full) trio closed under union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
.
A (full) AFL is a (full) semi-AFL closed under concatenation
Concatenation
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
and the Kleene plus.
Some families of languages
The following are some simple results from the study of abstract families of languages.Within the Chomsky hierarchy
Chomsky hierarchy
Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy is a containment hierarchy of classes of formal grammars....
, the regular language
Regular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
s, the context-free language
Context-free language
In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
s, and the recursively enumerable language
Recursively enumerable language
In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-acceptable. It is known as a type-0 language in the Chomsky hierarchy of formal languages...
s are all full AFLs. However, the context sensitive languages
Context-sensitive language
In theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy...
and the recursive language
Recursive language
In mathematics, logic and computer science, a formal language is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language...
s are AFLs, but not full AFLs because they are not closed under arbitrary homomorphisms.
The family of regular languages are contained within any cone (full trio). Other categories of abstract families are identifiable by closure under other operations such as shuffle, reversal, or substitution.
Origins
Seymour GinsburgSeymour Ginsburg
Seymour Ginsburg was a pioneer of automata theory, formal language theory, anddatabase theory, in particular; and computer science, in general...
of the University of Southern California
University of Southern California
The University of Southern California is a private, not-for-profit, nonsectarian, research university located in Los Angeles, California, United States. USC was founded in 1880, making it California's oldest private research university...
and Sheila Greibach
Sheila Greibach
Sheila Adele Greibach is a researcher in formal languages, automata,compiler theory in particular; and computer science in general. She is currently Professor of Computer Science at the University of California, Los Angeles....
of Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
presented the first AFL theory paper at the IEEE Eighth Annual Symposium on Switching and Automata Theory in 1967.