Automates à états finis et langages réguliers
Présentation du livre
La théorie des langages est une branche fondamentale de l'informatique dont les concepts se retrouvent dans de nombreuses disciplines comme la conception de processeurs, la compilation de logiciels, l'intelligence artificielle...
Cette discipline qui repose sur des concepts mathématiques fait partie des connaissances théoriques indispensables pour toute formation solide en informatique. Elle est enseignée dès la licence dans certains cursus.
Ce manuel est constitué de rappels de cours et de plus de 150 exercices avec leur corrigé détaillé.
Sommaire de l'ouvrage
Rappels et notations. Automates à états finis et déterministes. Langage reconnu par un automate. Fonctions de transition d'un automate. Automate complet et automate complété. Automate complémentaire. Successeurs et prédécesseurs d'un état. Détection d'un état. Détection de cycles. Equivalence et distinguabilité entre états. Minimisation. Détermination des automates à états finis non-déterministes (AEFND). Langage et AEFND. Algorithmes et AEFND. Modélisation et résolution de problèmes avec les automates. Expressions régulières. Grammaires régulières. Propriétés de l'itération.
