Abstract family of languages

An abstract family of languages is a grouping of formal languages such that the membership of a language in a given family is proven by its sharing of specific characteristics with the languages already known to be of that family. A family must contain at least one non-empty language, and while there may be no limit to the size of alphabets in the languages of a family, there must be a finite alphabet over which each of the languages in the family are defined. [http://eom.springer.de/A/a110110.htm Springer, "abstract family of languages"] ]

Formal definitions

A "formal language" is a set $L$ for which there exists a finite set of abstract symbols $Sigma$ such that $L\; subseteqSigma^*$, where * is the Kleene star operation.

A "family of languages" is an ordered pair $(Sigma,Lambda)$, where
# $Sigma$ is an infinite set of symbols;
# $Lambda$ is a set of formal languages;
# For each $L$ in $Lambda$ there exists a finite subset $Sigma\_1$ ⊂ $Sigma$ such that $L$ ⊆ $Sigma\_1^*$; and
# $L$ ≠ Ø for some $L$ in $Lambda$.

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.

ome families of languages

The following are some simple results from the study of abstract families of languages.Seymour Ginsburg, "Algebraic and automata theoretic properties of formal languages", North-Holland, 1975, ISBN 0 7204 2506 9.]

Within the Chomsky hierarchy, the regular languages, the context-free languages, and the recursively enumerable languages are all full AFLs. However, the context sensitive languages and the recursive languages 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. [http://eom.springer.de/a/a110430.htm Springer, "AFL operations"] ]

Origins

Seymour Ginsburg of the University of Southern California and Sheila Greibach of Harvard University first presented their AFL theory paper at the IEEE Eighth Annual Symposium on Switching and Automata Theory in 1967. [ [http://www.worldcat.org/oclc/2891921 IEEE conference record of 1967 Eighth Annual Symposium on Switching and Automata Theory] : papers presented at the Eighth Annual Symposium, University of Texas, October 18-20, 1967.]

References

* Mateescu, A; A. Salomaa. "Aspects of classical language theory" from cite book | last = Rozenburg | first = G. (ed) | coauthors = A. Salomaa (ed) | title = Handbook of Formal Languages | location = New York; Berlin | publisher = Springer-Verlag | year = 1997 | pages = pp. 175–251 | id = ISBN 3540614869

* Springer Encyclopaedia of Mathematics (online)