title: Famille abstraite de langages
text: # 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.
  
  