= Full abstract family of languages
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)=\varepsilon$ sends $\{a^nb^n:n\geq0\}$ to $\{a^n:n\geq0\}$. 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.<Studies in Abstract Families of Languages by Seymour Ginsburg and others>[First paper, Abstract families of languages, closure framework]{ref}
Back to article page
