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

, in particular in the field of

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of sym ...

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) is a language generated by a context-free grammar (CFG). Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by ...

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 computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics, it is more commonly known as the free monoid ...

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 \subset \Sigma

such that

L \subseteq \Sigma_1^*

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

closed Closed may refer to: Mathematics * Closure (mathematics), a set, along with operations, for which applying those operations on members always results in a member of the set * Closed set, a set which contains all its limit points * Closed interval, ...

under e-free homomorphism, inverse

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 ...

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

cone A cone is a three-dimensional geometric shape that tapers smoothly from a flat base (frequently, though not necessarily, circular) to a point called the apex or vertex. A cone is formed by a set of line segments, half-lines, or lines con ...

,'' 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 formalisations of concatenat ...

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 In formal language theory, computer science and linguistics, the Chomsky hierarchy (also referred to as the Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars. This hierarchy of grammars was described by ...

, 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 formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the ...

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 Seymour Ginsburg (December 12, 1927 – December 5, 2004) was an American pioneer of automata theory, formal language theory, and database theory, in particular; and computer science, in general. His work was influential in distinguishing theo ...

of the

University of Southern California , mottoeng = "Let whoever earns the palm bear it" , religious_affiliation = Nonsectarian—historically Methodist , established = , accreditation = WSCUC , type = Private research university , academic_affiliations = , endowment = $8.1 ...

and

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

Harvard University Harvard University is a private Ivy League research university in Cambridge, Massachusetts. Founded in 1636 as Harvard College and named for its first benefactor, the Puritan clergyman John Harvard, it is the oldest institution of highe ...

presented the first AFL theory paper at the IEEE Eighth Annual

Symposium on Switching and Automata Theory The IEEE Annual Symposium on Foundations of Computer Science (FOCS) is an academic conference in the field of theoretical computer science. FOCS is sponsored by the IEEE Computer Society. As writes, FOCS and its annual Association for Computing ...

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 ''Introduction to Automata Theory, Languages, and Computation'' is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation. Rajeev Motwani contributed to later editions beg ...

'', 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