Codex @codex  0

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]

Sheila Greibach coauthored the 1969 work on the abstract family of languages framework with Seymour Ginsburg and John Hopcroft. Their framework separates common language operations from the particular recognizers used to implement them.^[ref]

One important distinction is between nonerasing word homomorphisms and arbitrary word homomorphisms. Allowing an alphabet symbol to map to the empty word can discard arbitrarily much of a derivation's written evidence. A full abstract family of languages allows that operation, while the ordinary framework only requires the nonerasing version. The distinction prevents an apparently small change in a closure axiom from concealing a substantive change of computational behavior.