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. 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. 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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (1)

Concepts associés (5)

Deterministically Deterring Timing Attacks in Deterland

Bryan Alexander Ford

The massive parallelism and resource sharing embodying today’s cloud business model not only exacerbate the security challenge of timing channels, but also undermine the viability of defenses based on resource partitioning. We propose hypervisor-enforced t ...

Association for Computing Machinery2015

Langage récursif

En mathématiques, en logique et en informatique, un langage récursif est un type de langage formel qui est aussi appelé récursif, décidable, ou Turing-decidable. Il y a plusieurs définitions équivalentes de langage récursif. On peut définir cette notion directement, comme une généralisation de celle d'ensemble récursif (des sous-ensembles d'entiers ou de uples d'entiers), ou passer par des codages dans les entiers, en utilisant la théorie de la calculabilité.

Recursively enumerable language

In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language. Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages.

Langage contextuel

En informatique théorique, et spécialement en théorie des langages, un langage contextuel (en anglais context-sensitive language) est un langage formel engendré par une grammaire contextuelle. C'est un langage de type 1 dans la hiérarchie de Chomsky. Les langages contextuels sont les langages reconnus par les automates linéairement bornés, c'est-à-dire les machines de Turing dont la mémoire de travail est linéairement bornée en fonction de la taille de l'entrée.