Famille abstraite de langages
# Famille abstraite de langages

En informatique théorique, et en particulier en théorie des langages formels, le terme famille abstraite de langages réfère à une notion qui généralise des caractéristiques communes aux langage rationnels, aux langages algébriques, aux langages récursivement énumérables et à de nombreuses autres familles de langages formels.

## Définitions

* Un langage formel est un ensemble $L$ de mots sur un alphabet fini $A$, c'est-à-dire une partie du monoïde libre $A^{*}$, où * dénote l'étoile de Kleene.
* Une famille de langages est un couple formé d'un alphabet infini noté $\Sigma$ et, pour toute partie finie $A$ de $\Sigma$, d'un ensemble de langages formels sur $A$.
* Un cône rationnel (appelé full trio en anglais) est une famille de langages fermée pour les opérations de morphisme, de morphisme inverse, et d'intersection avec les langages rationnels.
* Un cône rationnel fidèle (appelé trio en anglais) est une famille de langages fermée pour les opérations de morphisme non effaçant, de morphisme inverse, et d'intersection avec les langages rationnels.
* Une famille de langages est rationnellement fermée si elle est fermée pour les opérations d'union, de produit, et d'étoile de Kleene.
* Une famille abstraite de langages (full abstract family of languages ou full AFL en anglais) est un cône rationnel qui en plus est rationnellement fermé.
* Une famille abstraite de langages fidèle (abstract family of languages ou AFL en anglais) est un cône rationnel fidèle rationnellement fermé.

On rencontre aussi la notion de semi-AFL pour un cône rationnel fermé par union.

## Exemples de familles abstraites de langages et propriétés

* Les langages rationnels forment une famille abstraite de langages.
* Les langages algébriques forment une famille abstraite de langages.
* Les langages contextuels forment une famille abstraite de langages fidèle, parce qu'ils ne sont pas fermés par morphisme quelconque.
* Les langages récursivement énumérables forment une famille abstraite de langages fidèle ainsi que les langages récursifs.
* Tout cône rationnel contient la famille des langages rationnels.
* Les langages linéaires forment un cône rationnel fermé par union. De même, les langages quasi-rationnels forment un cône rationnel fermé par union. Les langages linéaires ne sont pas rationnellement fermés, les langages quasi-rationnels le sont.
* D'autres opérations ne s'expriment pas au moyen des opérations de transduction rationnelle ou de fermeture pour les opérations rationnelles. Ce sont notamment le mélange (shuffle), l'image miroir, les substitutions.

## Origine

Le premier article traitant des familles abstraites de langages a été présenté par Seymour Ginsburg et Sheila Greibach au huitième symposium de la série Symposium on Switching and Automata Theory en 1967.

