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 ($L_1L_2 = \{xy : x \in L_1,\,y \in L_2 \}$), Kleene ${+}$ ($L^{+} = \cup_{n=1}^\infty L^n$, where $L^0 = \{\lambda\}$ and $L^{i+1} = L L^i$, $i \ge 0$, with $\lambda$ denoting the empty string), intersection with regular languages, morphisms (non-erasing in the context-sensitive case), and inverse morphisms (if $h : V^* \rightarrow U^*$ is a morphism, one says that $H^{-1} : U^* \rightarrow \mathcal{P}V^*$ defined by $$ h^{-1}(x) = \{ y \in V^* : h(y) = x \} $$ is an inverse morphism).

These six operations are called AFL operations, and a family of languages closed under them is called an abstract family of languages (AFL) (a full AFL when it is closed under arbitrary morphisms; cf. also Trio). Union, concatenation, and Kleene ${+}$ are also called regular operations.

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

1) union, Kleene ${+}$, non-erasing morphisms, inverse morphisms, and intersection with regular languages is closed under concatenation;

2) concatenation, Kleene ${+}$, 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). 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 $\mathcal{F}$; by replacing each symbol in each string of a regular language by the associated language one obtains a language in $\mathcal{F}$). 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

[a1]	J. Berstel, "Transductions and context-free languages" , Teubner (1979)
[a2]	S. Ginsburg, "Algebraic and automata-theoretic properties of formal languages" , North-Holland (1975)
[a3]	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)
[a4]	J.E. Hopcroft, J.D. Ullman, "Introduction to automata theory, languages, and computation" , Addison-Wesley (1979)
[a5]	"Handbook of Formal Languages" G. Rozenberg (ed.) A. Salomaa (ed.) , Springer (1997)
[a6]	A. Salomaa, "Formal languages" , Acad. Press (1973)

{[TEX|done}}