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]

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.

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 positive closure of a formal language $L$ is the language of all concatenations of one or more words from $L$:Here $L^n$ is $n$-fold concatenation of formal languages, while the Kleene star also permits $n=0$, whose contribution is the empty word $\epsilon$. Thus $L^{\ast }=L^{+}\cup \{\epsilon \}$.

For $L=\{ab\}$, positive closure is $\{ab,abab,ababab,\dots \}$. If $\epsilon \in L$, then $\epsilon \in L^{+}$ as well: positive counts chosen words, not their total character length. For the empty language, ${\varnothing }^{+}=\varnothing$ but ${\varnothing }^{\ast }=\{\epsilon \}$. This operation preserves regular languages and is one of the closure requirements in an abstract family of languages.

Seymour Ginsburg coauthored the 1969 studies of the abstract family of languages framework with Sheila Greibach and John Hopcroft. This approach compares formal-language classes through closure properties instead of one particular grammar or machine presentation.^[ref]

For example, closure under intersection with regular languages permits restricting an existing language by a finite-state filter. That property is weaker than closure under arbitrary intersections: two context-free languages can have a non-context-free intersection. Stating the allowed operation precisely keeps a shared abstract framework from incorrectly identifying different language classes.

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.