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[modifier | modifier le code]
- 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é 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[modifier | modifier le code]
- 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[modifier | modifier le code]
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].
Notes[modifier | modifier le code]
Références[modifier | modifier le code]
- (en) Seymour Ginsburg et Sheila Greibach, « Abstract Families of Languages », dans Eighth Annual Symposium on Switching and Automata Theory, 18-20 October 1967, Austin, Texas, USA, IEEE, , p. 128-139
- (en) Seymour Ginsburg, Algebraic and Automata Theoretic Properties of Formal Languages, North-Holland, (ISBN 0-7204-2506-9)
- (en) John E. Hopcroft et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, (ISBN 0-201-02988-X), « Chapitre 11: Closure properties of families of languages »
- (en) Alexandru Mateescu et Arto Salomaa, « Chapter 4: Aspects of Classical Language Theory », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1 : Word, Language, Grammar, Springer Verlag, (ISBN 978-3540604204), p. 175-252
