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.^[1] In mathematics, logic, and computer science, a formal language is a set of finite-length words (i. ...

Closure under AFL operations

The defining characteristic or property that proves membership for a particular formal language in an abstract family of languages is closure over some or all of the AFL operations:^[2]

• Union

• Concatenation

• Kleene+ (concatenation closure), such that

, where L⁰ is the empty string λ and L^{i + 1} = LⁱL for all i greater than or equal to zero.

• Intersection with the regular languages

• Morphism or homomorphism (non-erasing)

• Inverse morphism or inverse homomorphism

In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ... In formal language theory (and therefore in programming languages), concatenation is the operation of joining two character strings end to end. ... In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements. ... A regular language is a formal language (i. ... In mathematics, a morphism is an abstraction of a structure-preserving process between two mathematical structures. ... In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures (such as groups, rings, or vector spaces). ...

Some abstract families

There are three main families.^[3]

• A cone is a family of languages with closure under homomorphism, inverse homomorphism, and intersection with regular languages.

• An AFL is a family of languages with closure under λ-free homomorphism (where λ is the empty string), inverse homomorphism, union, intersection with regular languages, concatenation, and λ-free Kleene+.

• A full AFL is a cone with further closure under concatenation, Kleene+ and union operations.

The family of regular languages are contained within any cone. Other families are identifiable by closure under other operations such as shuttle, reversal, or substitution.^[4]

Origins

Seymour Ginsburg and Sheila Greibach of the University of Southern California first presented their AFL theory paper at the IEEE Eighth Annual Symposium on Switching and Automata Theory in 1967.^[5] Seymour Ginsburg (1928-2004) was a pioneer of automata theory, formal language theory, and database theory in particular; and computer science in general. ... Sheila Greibach (1939-) is a researcher in formal languages, automata, compiler theory in particular; and computer science in general. ... Doheny Library. ... The Institute of Electrical and Electronics Engineers or IEEE (pronounced as eye-triple-ee) is an international non-profit, professional organization incorporated in the State of New York, United States. ...

References

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

• Mateescu, A; A. Salomaa. "Aspects of classical language theory" from Rozenburg, G. (ed); A. Salomaa (ed) (1997). Handbook of Formal Languages. New York; Berlin: Springer-Verlag, pp. 175–251. ISBN 3540614869. 

• Springer Encyclopaedia of Mathematics (online)

Notes

1. ^ Springer, "abstract family of languages"
2. ^ Springer, "AFL operations"
3. ^ Springer, "abstract family of languages"
4. ^ Springer, "AFL operations"
5. ^ IEEE