Famille abstraite de langages

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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]

  • 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[modifier | modifier le code]

  • Les langages contextuels forment une famille abstraite de langages fidèle, parce qu'ils ne sont pas fermés par morphisme quelconque.
  • 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]

  1. Ginsburg et Greibach (1967)

Références[modifier | modifier le code]

  • 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,‎ 1967
  • Seymour Ginsburg, Algebraic and Automata Theoretic Properties of Formal Languages, North-Holland,‎ 1975 (ISBN 0-7204-2506-9)
  • John E. Hopcroft et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley,‎ 1979 (ISBN 0-201-02988-X), « Chapitre 11: Closure properties of families of languages »
  • Alexandru Mateescu et Arto Salomaa, « Chapitre 4: Aspects of Classical Language Theory », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1 : Word, Language, Grammar, Springer Verlag,‎ 1997 (ISBN 978-3540604204), p. 175-252

Voir aussi[modifier | modifier le code]