Trio

A non-trivial family of languages that is closed under three of the six natural closure operations (cf. Abstract family of languages; AFL operations). Initiated in [a2], the theory of abstract families of languages, AFL-theory, is a framework for systematically studying the closure properties of families of languages under certain operations. The starting point is the observation that the four basic families in the Chomsky hierarchy, the families of regular (REG), context-free (CF), context-sensitive (CS), and recursively enumerable (RE) languages, have similar closure properties; more specifically, all these families are closed under six important operations, the so-called AFL operations; moreover, also the proof techniques for such results are similar.

These six operations are: union, concatenation, Kleene closure ${+}$, intersection with regular languages, morphisms, and inverse morphisms.

A non-trivial family of languages (that is, a family containing at least one non-empty language) is called a trio (sometimes one uses the term cone; see also Abstract family of languages) if it is closed under non-erasing morphisms, inverse morphisms and intersection with regular languages. A trio closed under union is called a semi-AFL. A semi-AFL closed under concatenation and Kleene ${+}$ is called an AFL. A trio (semi-AFL, AFL) is said to be full if it is closed under arbitrary morphisms (and Kleene ${+}$ in the case of AFLs). A family of languages closed under none of the six AFL operations is called an anti-AFL.

The family REG is the smallest full trio; the families REG, CF, RE are full-AFLs, whereas CS is an AFL which is not full (in fact, each language in RE is the morphic image of a language in CS). The family of linear languages is a full semi-AFL not closed under concatenation and Kleene ${+}$. Examples of anti-AFLs can be found, for example, in the area of Lindenmayer systems [a3].

The six AFL operations are not independent. Hence, to show that a family of languages is an AFL one does not need to show closure under all six operations. (See AFL operations for results of this type.) Moreover, closure under certain other operations implies closure under AFL operations and, conversely, knowing that a family of languages is an AFL one obtain its closure under certain other operations. For instance, each substitution-closed trio is an AFL, whereas every trio is closed under substitution with $\lambda$-free regular languages ($\lambda$ is the empty string), under non-erasing generalized sequential machine mappings and under inverse generalized sequential machine mappings; any full trio is closed under substitution with arbitrary regular languages, arbitrary generalized sequential machine mappings, left and right quotient with regular languages (e.g., the right quotient of $L_1$ with respect to $L_2$ is the language $\{x : xy \in L_1\ \text{for}\ y\in L_2 \}$).

A trio (semi-AFL, AFL) $\mathcal{F}$ is said to be principal if there is a language $L$ such that $\mathcal{F}$ is the least trio (semi-AFL, AFL, respectively) containing $L$; the language $L$ is called a generator of the family $\mathcal{F}$.

All four families in the Chomsky hierarchy are principal; for instance, from the Chomsky–Schützenberger characterization of context-free languages one sees that the Dyck languages are generators of CF.

Characterizations of AFLs in terms of abstract families of automata are also possible. Details can be found in [a1]; results like those mentioned above and bibliographical information can be found in AFL operations.

See also Formal languages and automata; Abstract family of languages.

References

[a1]	S. Ginsburg, "Algebraic and automata-theoretic properties of formal languages" , North-Holland (1975)
[a2]	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)
[a3]	G. Rozenberg, A. Salomaa, "The mathematical theory of $L$ systems" , Acad. Press (1980) Zbl 0508.68031