Transduction rationnelle

Transduction rationnelle

En informatique théorique, en linguistique, en théorie des automates et en théorie des langages, une transduction rationnelle est une transformation de mots et de langages définie par un transducteur fini ou au moyen d'une relation rationnelle.

Les transductions rationnelles ont été introduites et étudiées par C. C. Elgot et J. E. Mezei[1], par Marcel-Paul Schützenberger et Maurice Nivat, et employées notamment par Seymour Ginsburg (en) et Sheila Greibach (en) dans l'étude des langages algébriques.

Sommaire

Définition

Une relation rationnelle sur deux alphabets A et B est une partie rationnelle du monoïde produit A^*\times B^*. En d'autres termes, c'est un élément de la plus petite famille de parties de A^*\times B^* contenant la relation vide, les singletons, et fermées par union, produit, et l'opération étoile, c'est-à-dire passage au sous-monoïde engendré.

  • Le produit de deux éléments (x,y) et (x',y') de A^*\times B^* est le couple (xx',yy'), le produit de deux parties R et R' de A^*\times B^* est l'ensemble de RR'=\{rr'\mid r\in R, r'\in R'\}
  • L' étoile d'une partie R de A^*\times B^* est la partie R^*=\cup_{n\ge0}R^n, où Rn est le produit de n facteurs égaux à R.

Une transduction rationnelle de A * vers B * est une application de A * dans l'ensemble des parties de B * dont le graphe est une relation rationnelle[2]. Plus formellement, f: A^*\to B^* est une transduction rationnelle si \{(x,y)\mid y\in f(x)\} est une relation rationnelle; réciproquement, si R \subset A^*\times B^* est une relation rationnelle, la transduction de A * vers B * définie par x\mapsto\{y\in B^*\mid (x,y)\in R\} est une transduction rationnelle.

Certaines propriétés s'expriment plus simplement en termes de relation rationnelle, d'autre en termes de transduction rationnelle.

Transduction et transducteur

La fonction réalisée par un transducteur fini est une transduction rationnelle. Réciproquement, pour toute transduction rationnelle, il existe un transducteur fini qui la réalise.

Propriétés

  • Composition: Si f: A^*\to B^* et g: B^*\to C^* sont des transductions rationnelles, la transduction composée h: A^*\to C^* définie par
        h(x)=\{z\in C^*\mid \exists y\in B^*: y\in f(x)\text{ et }z\in g(y))\}
    est une transduction rationnelle.
  • Inverse :Si f: A^*\to B^* est une tranduction rationnelle, la transduction inverse f^{-1}: B^*\to A^* définie par x\in f^{-1}(y)\iff y\in f(x) est rationnelle.
  • Représentation par morphisme: Pour toute transduction rationnelle f: A^*\to B^*, il existe un alphabet C, deux morphismes \alpha: C^*\to A^* et \beta: C^*\to B^* et un langage rationnel K\subset C^* tels que
          f(x)=\beta(\alpha^{-1}(x)\cap K)
    pour tout x\in A^*.
  • Préservation: L'image d'un langage rationnel 'd'un langage alégbrique) par une transduction rationnelle est un langage rationnel (un langage algébrique).

Exemples de transductions rationnelles

  • Un morphisme est une transduction rationnelle
  • Un morphisme inverse est une transduction rationnelle
  • L'intersection avec un langage rationnel est une transduction rationnelle
  • La transduction qui, à un mot de x, associe l'ensemble de ses préfixes, resp. suffixes, facteurs, sous-mots, est une transduction rationnelle.

Cône rationnel

Un cône rationnel, est une famille de langages fermée par transduction rationnelle. D'après la propriété de représentation, il est équivalent de demander qu'une famille de langages est fermée par morphisme, morphisme inverse et intersection avec un langage rationnel.

Un cône rationnel est appelé full trio en anglais. La raison est qu'un cône est fermé par un « trio » d'opérations et que le morphisme peut être effaçant, ce que les américains notent par l'adjectif full.

Un cône fidèle est une famille de langages fermée par morphisme non effaçant, morphisme inverse et intersection avec un langage rationnel. C'est ce qui est appelé trio en anglais.


Les langages rationnels, les langages algébriques, mais aussi de nombres sous-familles des langages algébriques, comme les langages linéaires, les langages à un compteur, les langages quasi-rationnels forment des cônes rationnels. Les langages context-sensitifs forment un cône fidèle.

Un cône rationnel est principal s'il existe un langage (un générateur) tel que tout langage du cône est image de ce générateur par une transduction rationnelle. Le théorème de Chomsky-Schützenberger dit, dans une version un peu renforcée, que le cône des langages algébriques est principal, et que tout langage de Dyck sur au moins deux paires de parenthèses en est un générateur.

Notes

  1. ↑ Elgot et Mezei (1965)
  2. ↑ Il y a là un abus de notation: on écrit f: A^*\to B^* alors que l'on devrait écrire f: A^*\to \mathfrak{P}(B^*)

Références

  • Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003 (ISBN 978-2-7117-4807-5).
    Traduction anglaise avec corrections: Elements of Automata Theory, Cambridge University Press 2009, (ISBN 9780521844253)
     
  • (en) C. C. Elgot et J. E. Mezei, « On relations defined by generalized finite automata », dans IBM J. Res. and Develop., vol. 9, 1965, p. 47-68 
  • (en) Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975 (ISBN 0-7204-2506-9) 
  • (en) Jean Berstel et Luc Boasson, « Context-free Languages », dans Jan van Leeuwen (éditeurs), Handbook of Theoretical Computer Science, vol. B : : Formal Models and Semantics, Elsevier, 1990 (ISBN 978-0444880741) 


Liens internes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Transduction rationnelle de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Expression rationnelle — Pour les articles homonymes, voir régulier et rationnel. Une expression rationnelle ou expression régulière[1] est en informatique une chaîne de caractères que l’on appelle parfois un motif et qui décrit un ensemble de chaînes de caractères… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Automate fini — Pour les articles homonymes, voir Automate. Fig. 1 : Automate fini reconnaissant les écritures binaires des multiples de 3. Un automate fini (on dit parfois, par une traduction littér …   Wikipédia en Français

  • Langage algébrique — En théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui peut être engendré par une grammaire algébrique. De manière équivalente un langage algébrique est un langage reconnu par automate à pile. Les… …   Wikipédia en Français

  • Langage de Dyck — En informatique théorique, et plus spécialement en théorie des langages, les langages de Dyck sont des langages formels particuliers. Un langage de Dyck est l ensemble des mots bien parenthésés, sur un alphabet formé de parenthèses ouvrantes, et… …   Wikipédia en Français

  • Transducteur à états finis — En informatique théorique, en linguistique, et en particulier en théorie des automates, un transducteur fini (appelé aussi transducteur à états finis par une traduction maladroite de l anglais finite state transducer) est un automate fini avec… …   Wikipédia en Français

  • Langage rationnel — Les langages rationnels ou langages réguliers ou encore langages reconnaissables peuvent être décrits de plusieurs façons équivalentes: ce sont les langages décrits par les expressions régulières ou rationnelles,d où le nom de langages réguliers; …   Wikipédia en Français

  • Théorème de Kleene —  Ne doit pas être confondu avec Théorème de récursion de Kleene ni Théorème du point fixe de Kleene. En informatique théorique, et plus précisément en théorie des automates, le théorème de Kleene affirme qu un langage peut être décrit par… …   Wikipédia en Français

  • Automate cellulaire — À gauche, une règle locale simple : une cellule passe d un état (i) au suivant (i+1) dans le cycle d états dès que i+1 est présent dans au moins 3 cellules voisines. À droite, le résultat (complexe) de l application répétée de cette règle… …   Wikipédia en Français

  • Grammaire formelle — Une grammaire est un formalisme permettant de définir une syntaxe et donc un langage formel, c est à dire un ensemble de mots admissibles sur un alphabet donné. La notion de grammaire formelle est particulièrement utilisée en programmation… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”