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- 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- 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
modifierLe 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
modifierRéférences
modifier- (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
