View source for AFL operations

The basic families in the Chomsky hierarchy (the regular, context-free, context-sensitive, and recursively enumerable languages) are closed under union (the usual set operation), concatenation (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a1104301.png" />), Kleene <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a1104304.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a1104305.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a1104306.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a1104307.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a1104308.png" />, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a1104309.png" /> denoting the empty string), intersection with regular languages, morphisms (non-erasing in the context-sensitive case), and inverse morphisms (if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a11043010.png" /> is a morphism, one says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a11043011.png" /> defined by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a11043012.png" /></td> </tr></table>

is an inverse morphism).

These six operations are called AFL operations, and a family of languages closed under them is called an AFL (a full AFL when it is closed under arbitrary morphisms; cf. also [[Abstract family of languages|Abstract family of languages]]; [[Trio|Trio]]). Union, concatenation, and Kleene <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a11043013.png" /> are also called regular operations.

The AFL operations are not independent. For instance, any family of languages which is closed under

1) union, Kleene <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a11043014.png" />, non-erasing morphisms, inverse morphisms, and intersection with regular languages is closed under concatenation;

2) concatenation, Kleene <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a11043015.png" />, non-erasing morphisms, inverse morphisms, and intersection with regular languages is closed under union;

3) concatenation, non-erasing morphisms, and inverse morphisms is closed under intersection with regular languages.

Moreover, if a family of languages is closed under intersection with regular languages, union with regular languages, and substitution with regular languages, then it is also closed under inverse morphisms. A family of languages is closed under morphisms, inverse morphisms, and intersection with regular languages if and only if it is closed under sequential transducers (finite automata with outputs, allowing transitions on the empty string; when the transitions are defined only for non-empty strings, one obtains the notion of a generalized sequential machine, abbreviated gsm).

Thus, to check the closure properties of a family of languages under the AFL operations, one does not have to consider all six operations. On the other hand, the AFL operations can simulate other operations, such as direct and inverse gsm mappings, quotients by regular languages, etc. (see [[Trio|Trio]]). Each AFL that contains a language containing the empty string is also closed under substitution into regular languages (for each symbol of an alphabet one associates a language from an AFL <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a11043016.png" />; by replacing each symbol in each string of a regular language by the associated language one obtains a language in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110430/a11043017.png" />). This is important, because an AFL is not necessarily closed under substitution (or intersection, reversal, shuffle, etc). However, any AFL closed under intersection is closed under substitution.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Berstel,   "Transductions and context-free languages" , Teubner  (1979)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  S. Ginsburg,   "Algebraic and automata-theoretic properties of formal languages" , North-Holland  (1975)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  S. Ginsburg,   S.A. Greibach,   "Abstract families of languages"  S. Ginsburg (ed.)  S.A. Greibach (ed.)  J.E. Hopcroft (ed.) , ''Studies in Abstract Families of Languages'' , ''Memoirs'' , '''87''' , Amer. Math. Soc.  (1969)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J.E. Hopcroft,   J.D. Ullman,   "Introduction to automata theory, languages, and computation" , Addison-Wesley  (1979)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  "Handbook of Formal Languages"  G. Rozenberg (ed.)  A. Salomaa (ed.) , Springer  (1997)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  A. Salomaa,   "Formal languages" , Acad. Press  (1973)</TD></TR></table>