Abstract family of languages

An abstract family of languages is a family of formal languages containing a nonempty language and closed under finite union, concatenation of formal languages, positive closure of a formal language, nonerasing monoid homomorphisms between free word monoids, inverse homomorphisms, and intersection with regular languages. Here positive closure means $L^{+}={\bigcup }_{n\ge 1}{L}^n$, and nonerasing means that the homomorphism maps every alphabet letter to a nonempty word.

A full abstract family of languages allows arbitrary word homomorphisms, including ones that erase letters. This distinction matters: erasing an unbounded amount of a computation or derivation can change the resources needed to recognize the image language. The regular languages and context-free languages are full abstract families. In particular, the closure axioms say that if $L$ is context-free and $R$ is regular, then $L\cap R$ is context-free; they do not assert closure under intersection of two arbitrary context-free languages. The framework collects the common constructions without identifying the different language classes.^[ref]

A full abstract family of languages is an abstract family of languages closed under all word monoid homomorphisms, including those erasing letters. It retains the other closure requirements: finite union, concatenation of formal languages, positive closure of a formal language, inverse homomorphism, and intersection with regular languages.

For example, the homomorphism $h(a)=a$, $h(b)=\epsilon$ sends $\{a^n{b}^n:n\ge 0\}$ to $\{a^n:n\ge 0\}$. Such a map is excluded by a nonerasing-only homomorphism axiom. The adjective full says this additional erasure operation is allowed; it does not assert closure under every operation on languages.

Both regular languages and context-free languages form full abstract families. For the latter, intersection with a regular language is allowed, but intersection of two arbitrary context-free languages need not remain context-free. Erasing an arbitrarily long part of a representation can conceal unbounded intermediate work, so the distinction matters when comparing computational language classes.^[ref]

The axioms of an abstract family of languages require particular closure properties of formal languages. A language class is closed under an operation when applying that operation to members always produces another member of the class.