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 multiplicité et de sortie constituent alors un modèle assez puissant pour exprimer des propriétés non triviales et sont utilisés comme outil dans des domaines aussi variés que le traitement des langues naturelles, la vérification de systèmes et des protocoles, etc.. 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 qui la structure et l'organise.
L'objectif du module est de présenter les différentes facettes de ce modèle enrichi et de décrire sa puissance suivant les différents ensembles choisis pour les multiplicités et pour les relations entre mots. Les notions abordées dans le module pourront être illustrées et faire l'objet d'exercices à l'aide de la plateforme vaucanson.
Les calculs et constructions mis en oeuvre dans un bon nombre d'exercices pourront être réalisés sur la plateforme vaucanson .
Cette plateforme est installée sur la machine vcsn.enst.fr sur laquelle un compte sera ouvert pour chaque étudiant du cours INF 340. Il est également possible de télécharger la dernière version à partir du site de la plateforme et de l'installer sur un ordinateur personnel. Néanmoins cette installation n'est pas élémentaire (plusieurs autres bibliothèques doivent être également chargées au préalable).
Une documentation sur cette plateforme, ou plutôt sur son utilisation en lignes de commande, peut être téléchargée depuis le site de la plateforme ou, plus directement, ici. L'utilisation de vaucanson par les étudiants permettra sans doute d'apporter des corrections et des améliorations à ce document.