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 2es cycles d'informatique des
universités, plus quelques 1er et 3e cycles, mais aussi les
candidats à l'agrégation de mathématiques désirant choisir
l'option informatique.
Il met à la disposition des étudiants et enseignants un
recueil d'exercices et de problèmes — dont certains
sont énoncés dans les manuels de référence du domaine
— entièrement corrigés.
Pratique et synthétique, cet ouvrage adopte une
organisation systématique : pour chaque chapitre, deux ou
trois pages de rappels de cours, contenant uniquement les
notions introduites et les résultats les concernant, sont
suivies d'une douzaine d'exercices 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. A noter : lors de
l'utilisation de méthodes intuitives, celle d'algorithmes
prouvés est systématisée afin que le lecteur ait toujours
une méthode à laquelle se raccrocher.
Table des matières
Introduction
Chapitre 1 - Notions de mots et de langages
Chapitre 2 - Automates finis
Chapitre 3 - Langages reconnaissables
Chapitre 4 - Déterminisme – Minimalité
Chapitre 5 - Langages non reconnaissables
Chapitre 6 - Compléments
Chapitre 7 - Problèmes
Index