Abstract family of languages

Specific families of languages have emerged in the classical theory of formal languages as important and widely studied ones. Among such families are the families of regular, context-free, context-sensitive and recursively enumerable languages. (See Formal languages and automata.) In the theory of abstract families of languages, briefly AFL-theory, one investigates common properties of language families whose only defining property is closure under certain operations (the AFL operations): whenever one of the operations is applied to languages in the family (only unary or binary operations are considered here), then the resulting language is also in the family.

By definition, a family of languages is a set of languages possessing a non-empty language. The size of the alphabet of the individual languages in the family may grow beyond all bounds, but for every language $ L $ in the family there must exist a finite alphabet $ V _ {T} $ such that $ L $ is a language over $ V _ {T} $. A family of languages is called a cone if it is closed under homomorphism, inverse homomorphism and intersection with regular languages. A cone that is closed under union, catenation and catenation closure is a full AFL. An AFL is a family of languages closed under each of the following operations: $ \lambda $- free homomorphism, inverse homomorphism, intersection with regular languages, union, catenation, and $ \lambda $- free catenation closure.

So, the definitional (axiomatic) closure properties of each of the three types of families are as follows (the operation "intersection with regular languages" is abbreviated by $ \cap { \mathop{\rm Reg} } $).

Cone: homomorphism, inverse homomorphism, $ \cap { \mathop{\rm Reg} } $.

Full AFL: homomorphism, inverse homomorphism, $ \cap { \mathop{\rm Reg} } $, union, catenation, catenation closure.

AFL: $ \lambda $- free homomorphism, inverse homomorphism, $ \cap { \mathop{\rm REG} } $, union, catenation, $ \lambda $- free catenation closure.

For the definition of the various operations, see Formal languages and automata and AFL operations. The operations defining a cone are exactly the ones defining rational transductions. The operations defining a full AFL are the regular ones and rational transductions, since the latter can be expressed in terms of homomorphisms, inverse homomorphisms and $ \cap { \mathop{\rm REG} } $. This choice of terminology is a compromise between the original American (see [a2] and [a1]) and French (see [a4]) schools. The term "AFL" comes from the Americans, the term "cone" (depicting closure under rational transductions) from the French. The American counterpart of a cone is a "full triofull trio" (reflecting only the fact that three operations are involved; see also Trio), whereas the French use the name "FALFAL" (for "famille agréable de langages" ) for a full AFL.

AFL-theory contains numerous results (see [a1], [a5], [a3]) about further closure and other properties of cones and AFLs, as well as about possibilities of replacing the definitional operations by some other ones. For instance, the family of regular languages is contained in every cone. According to the main theorem of AFL-theory, the full AFL-closure of any language family $ {\mathcal L} $ is obtained by first closing $ {\mathcal L} $ under rational transductions, and then closing the resulting family under regular operations.

The generative point of view provides another approach for the study of language families (see Grammar form).

References

[a1]	S. Ginsburg, "Algebraic and automata-theoretic properties of formal languages" , North-Holland (1975)
[a2]	S. Ginsburg, S. Greibach, J. Hopcroft, "Studies in abstract families of languages" , Memoirs , 87 , Amer. Math. Soc. (1969)
[a3]	A. Mateescu, A. Salomaa, "Aspects of classical language theory" G. Rozenberg (ed.) A. Salomaa (ed.) , Handbook of Formal Languages , 1 , Springer (1997) pp. 175–251
[a4]	M. Nivat, "Transduction des langages de Chomsky" Ann. Inst. Fourier Grenoble , 18 (1968) pp. 339–455
[a5]	A. Salomaa, "Formal languages" , Acad. Press (1973)