You are here
Homeabstract family of languages
Primary tabs
abstract family of languages
Abstract families of languages are abstractions of the families of languages defined by the Chomsky hierarchy in that they are not necessarily defined by grammars, and yet share the same sets of closure operations as the Chomsky language families do.
We begin with a word about a family of languages. A family of languages is a defined as a pair $(V,\mathscr{L})$ of sets such that each $L\in\mathscr{L}$ is a language over some alphabet $\Sigma\subseteq V$. In practice, we omit $V$ and denote $\mathscr{L}$ as a family of languages. There is no restriction placed on the cardinality of $V$. Note that if $V$ is finite, then $\mathscr{L}$ is just a subset of the set $\mathscr{L}(V)$ of all languages over $V$. If $V$ is infinite, let us also denote $\mathscr{L}(V)$ to be the family of all languages over finite subsets of $V$.
Definition. Let $\mathscr{L}$ be a family of languages. Then $\mathscr{L}$ is defined as a ray, a cylinder, a trio, a cone, an abstract family of language or AFL, or a full AFL, if it contains a nonempty language, and is closed under the operations marked by X in the appropriate cells below.
operation  ray  cylinder  trio  cone  AFL  full AFL 

union  X  X  
homomorphism  X  X  
$\lambda$free homomorphism  X  X  
inverse homomorphism  X  X  X  X  X  X 
intersection with a regular language  X  X  X  X  X  
Kleene plus  X  X 
A cone is also called a full trio. It is clear that a family of languages is a full AFL iff it an AFL and a cone. We also have the following obvious implications:
$\xymatrix@R=2pt{\mbox{full AFL}\ar[rr]&&\mbox{cone}\ar[drr]&&&&\\ &&&&\mbox{cylider}\ar[rr]&&\mbox{ray}\\ \mbox{AFL}\ar[rr]&&\mbox{trio}\ar[urr]&&&&}$ 
However, none of the arrows can be reversed.
Moreover, we have the following:
Proposition 1.
The families $\mathscr{L}_{i}$ of languages, where $i=0,2,3$, defined by the Chomsky hierarchy, are all full AFL. $\mathscr{L}_{1}$ is an AFL not a full AFL.
There exists a cone that is not a full AFL (hence not an AFL). There exists an AFL (full AFL) that is not one of the Chomsky language families: the family of recursive languages is an AFL not a full AFL, and the family of indexed languages is a full AFL.
Below are some other closure properties related the specific families of languages defined above:

properties implying cones, AFLs, or full AFLs: let $\mathscr{L}$ be a family of languages,

if $\mathscr{L}$ contains a language containing a nonempty word, and is closed under union, Kleene plus, $\lambda$free regular substitution, intersection with a regular language, and restricted homomorphism, then it is an AFL.

if the restricted homomorphism in the above statement is replaced by an arbitrary homomorphism, then $\mathscr{L}$ is a full AFL

if $\mathscr{L}$ is $\lambda$free and contains all $\lambda$free regular languages, and is closed under intersection with regular languages, $\lambda$free substitution, and restricted homomorphism, then it is an AFL

if $\mathscr{L}$ contains $\mathscr{L}_{3}$, the family of all regular languages, and is closed under intersection with a regular language and substitution, then it is a full AFL


characterizations of cones, AFLs, or full AFLs: let $\mathscr{L}$ be a family of languages,

$\mathscr{L}$ is a cone iff it is closed under rational transduction

suppose $\mathscr{L}$ contains a language containing a nonempty word, then $\mathscr{L}$ is an AFL iff it is closed under union, Kleene plus, $\lambda$free regular substitution, intersection with a regular language, and restricted homomorphism

again suppose $\mathscr{L}$ contains a language containing a nonempty word, then $\mathscr{L}$ is an AFL iff it is closed under union, Kleene star, regular substitution, intersection with a regular language, and homomorphism


properties of cones, AFLs, or full AFLs:

Every cone contains $\mathscr{L}_{3}$.

An AFL is closed under concatenation, and so is a full AFL.

Every AFL contains the family of $\lambda$free regular languages.

If the AFL is not $\lambda$free (meaning it contains a language containing the empty word $\lambda$), then it contains $\mathscr{L}_{3}$. Furthermore, such an AFL is closed under Kleene star.

Every AFL is closed under $\lambda$free GSM mapping.

Every cone or full AFL is closed under GSM mapping.

Remark. When a family of languages satisfies none of the closure properties listed in the table above, it is said to be antiAFL. For example, the family of languages generated by Lsystems is antiAFL.
References
 1 S. Ginsburg, S. Greibach, J. Hopcroft, Studies in Abstract Families of Language. Memoirs of the American Mathematical Society, No.87, (1969).
 2 S. Ginsburg, E. Spanier, Substitution in families of languages. Information Sci. 2, (1970) pp 83110.
 3 A. Salomaa, Formal Languages, Academic Press, New York (1973).
 4 A. Mateescu, A. Salomaa, Handbook of Formal Languages: Volume 1. Word, Language, Grammar, Springer, (1997).
 5 N. Pippenger, Theories of Computability, Cambridge University Press (1997).
Mathematics Subject Classification
68Q70 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections