Théorie des automates

Cet ouvrage est à l'usage de l'ensemble des étudiants suivant un cours de théorie des langages formels - automates finis, langages algébriques -, c'est-à-dire la presque totalité des 2^es cycles d'informatique des universités, plus quelques 1^er et 3^e cycles, mais aussi les étudiants de classes préparatoires auxquels une option informatique, comportant un enseignement sur les automates finis, est proposée depuis trois ans.

Il met à la disposition des étudiants et enseignants un recueil d'exercices et de problèmes entièrement corrigés - dont certains sont énoncés dans les manuels de référence du domaine. Pratique et synthétique, cet ouvrage adopte une organisation systématique : pour chaque chapitre, quelques pages de rappels de cours, contenant uniquement les notions introduites et les résultats les concernant, sont suivies d'exercices corrigés les illustrant.

L'objectif de ces exercices n'est pas de présenter des solutions de résultats difficiles ou de longs problèmes, mais de donner des méthodes de résolution, parfois intuitives, d'exercices de base afin de familiariser le lecteur avec les notions essentielles et les techniques élémentaires de la théorie des automates. En plus de l'utilisation de méthodes intuitives, celle d'algorithmes prouvés est systématisée afin que le lecteur ait toujours une technique à laquelle se raccrocher.

Chapitre 1 - Nations de mots et de langage

Chapitre 2 - Automates finis

Chapitre 3 - Langages reconnaissables

Chapitre 4 - Déterminisme - Minimalité

Chapitre 5 - Langages non reconnaissable

Chapitre 6 - Compléments

Chapitre 7 - Problèmes