Si on cherche le mot «transducteur» dans une encyclopédie (une encyclopédie en ligne puisqu'il n'y a quasiment plus d'encyclopédie papier à la bibliothèque de l'Ecole), on trouve: «un transducteur est un dispositif convertissant un signal physique en un autre ; par exemple un signal lumineux en signal nerveux (vision animale) ou signal électrique (photorécepteur)». C'est évidemment un sujet fort intéressant, à la base de quasiment tous les instruments de mesure, de même que le cœur de tous les appareils de reproduction sonore. Mais ce n'est pas le sujet de ce cours.

Si on va au bout de la page, on voit quand même que les «transducteurs finis» sont un sujet qui relève de l'informatique, sont des «automates finis avec sorties», et c'est bien cela que nous allons étudier.

Les automates finis sont le modèle le plus simple de machines qui calculent, le premier dans toute hiérarchie des machines de Turing plus ou moins contraintes. Cette simplicité en fait un objet robuste, susceptible de nombreuses définitions équivalentes, relevant de la théorie de la complexité, de l'algèbre non-commutative et de la logique.

Les automates finis enrichis par les notions de sortie constituent alors un modèle assez puissant pour exprimer des propriétés non triviales et, indépendamment de leur rôle dans l'étude théorique des langages formels, sont utilisés comme outil aussi bien pour l'analyse syntaxique des langages de programmation que pour le traitement des langues naturelles, analyse morphologique ou analyse phonologique, pour la modélisation de l'arithmérique des ordinateurs, voire même en théorie des nombres.

Les problèmes rencontrés dans chacun de ces domaines, relèvent souvent de la théorie des automates et ne se heurtent pas immédiatement au mur de l'indécidabilité: il y a de l'espace pour des résultats profonds. Ainsi, cette théorie est-elle un chapitre de base de l'informatique théorique. L'objectif de ce cours est l'étude des transducteurs finis et des différentes sous-classes qu'on peut définir ainsi que des relations entre mots qu'ils réalisent.

Présentation générale

On commence par décrire le modèle et donner une série d'exemples qui permettent de cerner la puissance du modèle puis on établit la fermeture par composition des relations réalisées par les transducteurs finis qui montre que ce modèle est robuste et raisonnable (Leçon 1).

On fait ensuite le lien avec la notion de rationalité et on constate l'indécidabilité de l'équivalence qui laisse penser que le modèle des transducteurs finis est d'une certaine façon peut-être trop général (Leçon 2). Puis on définit la notion de morphisme pour ces automates généraux que sont les transducteurs et celle, plus précise, de revêtement qui assure une bijection entre les calculs (Leçon 3).

Dans la leçon suivante, on étudie la famille des transducteurs synchrones qui déterminent la famille de relations rationnelles la plus large sur laquelle les propriétés classiques des automates finis sur un monoïde libre (complémentation, décidabilité de l'équivalence, etc.) sont encore valides (Leçon 4).

Dans la Leçon 5, on prend un point de vue qui rompt la symétrie entre l'entrée et la sortie qui prévalait mais qui permet de retrouver la notion de reconnaissabilité via celle de représentation. Les deux dernières leçons traitent de familles particulières de transducteurs définies le plus naturellement par les propriétés des représentations qui leur correspondent. Les transducteurs fonctionnels (Leçon 6) et les transducteurs séquentiels (Leçon 7) sont sans doute les modèles le plus souvent utilisés dans la pratique et pour lesquels les propriétés d'appartenance à la famille et d'équivalence sont décidables.

*

Ce cours se place entre un cours élémentaire de théorie des langages et des grammaires, tel qu'il est dispensé en INF 105, et le cours que j'enseigne dans le cadre du MPRI dans l'option «Modèles de calcul et automates finis» et dans lequel j'étudie de façon plus systématique le modèle des automates avec multiplicité et avec sortie dans toute sa généralité.

Programme détaillé des leçons données en 2016/2017

• Table et Avant-propos   (version du 23/01/2017).

Leçon 1     —   23/11/16.     Le modèle «transducteur fini»

Dans cette leçon, on introduit le modèle des automates finis «avec sortie», qu'on appelle «transducteurs», et qui sont des automates (finis) sur des produits directs de monoïdes libres. Ce modèle de calcul est équivalent aux machines de Turing unidirectionnelles à 2 bandes (ou plus). On montre la fermeture par composition des relations de mots réalisées par les transducteurs.

• Matière traitée:

1. Définitions.     Automates sur un monoïde libre.   Transducteurs.   Relations réalisées par transducteurs finis.
2. Travail sur le modèle.     Normalisation.   Extensions.  
3. Composition.    

• Notes de cours   Leçon 1  

• Feuille d'exercices   Exercices 1  

Leçon 2     —     7/12/16.     Rationalité.

On donne une caractérisation algébrique des relations RTF, qu'on appellera désormais relations rationnelles. Elle résume ce qu'il peut y avoir de commun entre les langages rationnels, acceptés par les automates finis, et les relations RTF. On explore ensuite par contraste ce qui les différencie, jusqu'à arriver à l'indécidabilité de l'équivalence.

• Matière traitée:

1. Corrections des exercices de la leçon 1.    
2. Le théorème fondamental des automates finis.     Parties rationnelles d'un monoïde.   Le théorème fondamental.  
3. Rat A*xB*, des faits.     Intersection, complément.   Equivalence.   Ambiguïté.  
4. Preuve des résultats d'indécidabilité.     Le problème de correspondance de Post.  

• Notes de cours   Leçon 2  

• Feuille d'exercices   Exercices 2  

Leçon 3     —   14/12/16.     Morphismes et revêtements.

Étant donné un automate, on voudrait trouver un automate équivalent mais de dimension plus petite, et avec la contrainte de conserver la structure des calculs, c’est-à-dire qu’à chaque calcul de l’automate original, on sait faire correspondre un calcul de l’automate réduit.

Le problème que l’on se pose en fait est de décrire les conditions sous lesquelles cette réduction est « conforme », c’est-à-dire que les calculs du réduit sont tous des images de calcul de l’automate original. On montrera qu’on peut le faire de telle sorte qu’il existe un automate réduit minimal, au prix d’une rupture de la symétrie entre origine et destination des transitions.

On s’intéressera ensuite au cas où, dans ce contexte, il y a bijection entre les calculs de l’automate de départ et l’automate réduit. On verra par la suite que cette construction est intéressante « dans les deux sens », dans le sens de la réduction, biensûr, mais aussi dans le sens de l’expansion, qui revient à désintriquer les calculs de l’automate original.

• Matière traitée:

1. L'automate minimal d'un langage.    
2. Morphismes d'automates.     Propriétés locales des morphismes.    
3. Out-morphimes et quotients.     Le revêtement de Schützenberger.

• Notes de cours   Leçon 3   avec corrections (version du 23/01/2017).

• Feuille d'exercices   Exercices 3  

Leçon 4     —     4/01/17.     Transducteurs et relations synchrones.

Le modèle des transducteurs que nous avons décrits à la leçon 1 définit une famille de relations en un sens trop générale puisqu'une question aussi simple que l'universalité y est indécidable.

Cette famille a également le défaut de ne pas être fermée par complémentation, ce qui exclut toute possibilité de définition en terme de logique.

Le sujet de cette leçon est la définition d'une classe restreinte de relations rationnelles qu'on appellera \emph{relations synchrones}, toujours à partir des transducteurs qui les réalisent, et qui va jouir d'à peu près toutes les bonnes propriétés des langages rationnels d'un monoïde libre: complémentation, décidabilité de l'équivalence, etc.

• Matière traitée:

1. Corrections des exercices de la leçon 3.    
2. Définitions et exemples.     Transducteurs synchrones.   Relations synchrones.  
3. Propriétés des relations synchrones.     Déterminisation et complémentation.   Composition.  

• Notes de cours   Leçon 4   (version du 9/01/2017).

• Feuille d'exercices   Exercices 4  

Leçon 5     —   11/01/17.     Transducteurs «temps-réel».

Dans cette leçon, on va adopter un point de vue sur les transducteurs qui rompt complètement avec la symétrie entre la première et la deuxième composante des étiquetes des transitions, entre l'entrée et la sortie. Ces transducteurs d'un nouveau genre pourront être vu comme des automates sur un monoïde libre, donc chaque transition est étiquetée par une lettre, qui sera l'entrée, accompagnée d'un poids, qui sera la sortie.

Cette transformation se développe naturellement à l'aide d'un nouvel outil mathématique pour la description des automates: la réalisation par représentation matricielle. Les théorèmes d'évaluation et de composition en seront transformés. Mais surtout, ce point de vue ouvre la voie à la définition et à l'étude de nouvelles classes de relations: les relations séquentielles et les relations fonctionnelles qui seront les sujets des leçons suivantes.

• Matière traitée:

1. Représentation matricielle des automates classiques.     Parties reconnaissables d'un monoïde.  
2. Transducteurs «temps-réel».    
3. Représentation matricielle des relations rationnelles.    

• Notes de cours   Leçon 5   (version du 16/01/2017).

• Feuille d'exercices   Exercices 5  

Leçon 6     —   18/01/17.     Transducteurs «temps-réel» (suite).

• Matière traitée:

1. Théorèmes d'évaluation et de composition.     Composition des représentations
2. Uniformisation des relations rationnelles    
3. Relations rationnelles fonctionnelles.    

• Notes de cours   Leçon 5   complétée (version du 23/01/2017).

• Feuille d'exercices   Exercices 6  

Leçon 7     —   25/01/17.     Transducteurs séquentiels.

• Matière traitée:

1. Définition et exemples.
2. Décider la séquentialité.    Plus long préfixe commun,   Déterminisation,   Séquentialisation,   Propriété de jumelage.

Leçon 8     —    1/02/17.     Travaux dirigés de révision.

Contrôle des connaissances.     —     3/02/17.    

Enoncé     Enoncé (English)     Corrigé     Corrigé (English)    

Documentation complémentaire

• Annales    —    Contrôle des connaissances 2015/2016:    Enoncé     Corrigé