= Abstract family of languages
{wiki}
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\geq1}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.<Studies in Abstract Families of Languages by Seymour Ginsburg and others>[First paper, Abstract families of languages, printed pp.1–32, closure-axiom framework]{ref}
Back to article page
