Famille abstraite de langages
Aller à la navigation
Aller à la recherche
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 de mots sur un alphabet fini , c'est-à-dire une partie du monoïde libre , où * dénote l'étoile de Kleene.
- Une famille de langages est un couple formé d'un alphabet infini noté et, pour toute partie finie de , d'un ensemble de langages formels sur .
- Un cône rationnel (appelé Modèle:Langue 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é Modèle:Langue 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 (Modèle:Langue ou Modèle:Langue en anglais) est un cône rationnel qui en plus est rationnellement fermé.
- Une famille abstraite de langages fidèle (Modèle:Langue ou Modèle:Langue en anglais) est un cône rationnel fidèle rationnellement fermé.
On rencontre aussi la notion de Modèle:Langue 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 (Modèle:Langue), 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[1].