computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

, in particular in the field of

formal language In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet". The alphabet of a formal language consists of symbols that concatenate into strings (also c ...

theory, an abstract family of languages is an abstract mathematical notion generalizing characteristics common to the

regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...

s, the

context-free language In formal language theory, a context-free language (CFL), also called a Chomsky type-2 language, is a language generated by a context-free grammar (CFG). Context-free languages have many applications in programming languages, in particular, mos ...

s and the

recursively enumerable language In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set o ...

s, and other families of formal languages studied in the scientific literature.

Formal definitions

A ''formal language'' is a set for which there exists a finite set of abstract symbols such that

L \subseteq\Sigma^*

, where * is the

Kleene star In mathematical logic and theoretical computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation on a Set (mathematics), set to generate a set of all finite-length strings that are composed of zero or more repe ...

operation. A ''family of languages'' is an ordered pair

(\Sigma,\Lambda)

, where # is an infinite set of symbols; # is a set of formal languages; # For each in there exists a finite subset

\Sigma_1 \subseteq \Sigma

such that

L \subseteq \Sigma_1^*

; and # for some in . A ''trio'' is a family of languages closed under

homomorphism In algebra, a homomorphism is a morphism, structure-preserving map (mathematics), map between two algebraic structures of the same type (such as two group (mathematics), groups, two ring (mathematics), rings, or two vector spaces). The word ''homo ...

s that do not introduce the empty word, inverse

s, and intersections with a regular language. A ''full trio,'' also called a ''

cone In geometry, a cone is a three-dimensional figure that tapers smoothly from a flat base (typically a circle) to a point not contained in the base, called the '' apex'' or '' vertex''. A cone is formed by a set of line segments, half-lines ...

,'' 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 In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalizations of concatenati ...

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 The Chomsky hierarchy in the fields of formal language theory, computer science, and linguistics, is a containment hierarchy of classes of formal grammars. A formal grammar describes how to form strings from a formal language's alphabet that are v ...

, the regular languages, the context-free languages, and the recursively enumerable languages are all full AFLs. However, the context sensitive languages and the

recursive language In mathematics, logic and computer science, a recursive (or ''decidable'') language is a recursive subset of the Kleene closure of an alphabet. Equivalently, a formal language is recursive if there exists a Turing machine that decides the forma ...

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 Ginsburg of the

University of Southern California The University of Southern California (USC, SC, or Southern Cal) is a Private university, private research university in Los Angeles, California, United States. Founded in 1880 by Robert M. Widney, it is the oldest private research university in ...

and

Sheila Greibach Sheila Adele Greibach (born 6 October 1939 in New York City) is an American researcher in formal languages in computing, automata, compiler theory and computer science. She is an Emeritus Professor of Computer Science at the University of Calif ...

Harvard University Harvard University is a Private university, private Ivy League research university in Cambridge, Massachusetts, United States. Founded in 1636 and named for its first benefactor, the History of the Puritans in North America, Puritan clergyma ...

presented the first AFL theory paper at the IEEE Eighth Annual Symposium on Switching and Automata Theory in 1967.

Notes

References

* *Seymour Ginsburg, ''Algebraic and automata theoretic properties of formal languages'', North-Holland, 1975, . * John E. Hopcroft and Jeffrey D. Ullman, '' Introduction to Automata Theory, Languages, and Computation'', Addison-Wesley Publishing, Reading Massachusetts, 1979. . Chapter 11: Closure properties of families of languages. * {{cite book , last1=Mateescu , first1=Alexandru , last2=Salomaa, first2=Arto , editor1-first=Grzegorz, editor1-last=Rozenberg, editor2-first=Arto, editor2-last=Salomaa , title=Handbook of Formal Languages. Volume I: Word, language, grammar , publisher=Springer-Verlag , year=1997 , pages=175–252 , chapter=Chapter 4: Aspects of Classical Language Theory , isbn=3-540-61486-9 Formal languages Applied mathematics