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 of sets such that each is a language over some alphabet $\Sigma\subseteq V$ . In practice, we omit $V$ and denote as a family of languages. There is no restriction placed on the cardinality of $V$ . Note that if $V$ is finite, then is just a subset of the set of all languages over $V$ . If $V$ is infinite, let us also denote to be the family of all languages over finite subsets of $V$ .

Definition. Let be a family of languages. Then 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 non-empty language, and is closed under the operations marked by X in the appropriate cells below.

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:

Moreover, we have the following:

Proposition 1   The families of languages, where $i=0,2,3$ , defined by the Chomsky hierarchy, are all full AFL. 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 be a family of languages,
  • if contains a language containing a non-empty 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 is a full AFL
  • if 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 contains , 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 be a family of languages,
  • is a cone iff it is closed under rational transduction
  • suppose contains a language containing a non-empty word, then 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 contains a language containing a non-empty word, then 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 .
  • 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 . 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 anti-AFL. For example, the family of languages generated by L-systems is anti-AFL.

Bibliography

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 83-110.

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).