Automates et langages

Introduction à la théorie des automates et des machines à états finis, des langages formels, et découverte de leurs principales applications

Prérequis

Outils formels pour l’informatique

Description

Ce cours présente la théorie classique des automates et des langages formels. Il s’appuie sur la hiérarchie de Chomsky pour les langages et présente successivement les langages réguliers, les expressions régulières, les automates finis, les grammaires régulières et le théorème de Kleene. Les algorithmes de déterminisation, minimisation et de passage d’un modèle à un autre ainsi que les propriétés de clôture y sont décrits en détail. Les démonstrations se font le plus souvent par construction, par induction ou de façon algorithmique. Des grammaires régulières, le cours passe aux grammaires algébriques, aux langages contextuels et aux automates à pile. Là encore, les relations entre les différents modèles et les propriétés de clôture sont étudiés. Le cours se poursuit avec les formes spéciales des grammaires et le problème de l’appartenance, ainsi que les algorithmes correspondant, en particulier, celui de Cocke Youger et Kasami. Le cours se termine sur l’étude des machines de Turing et une brève évocation de la théorie de la calculabilité avec la notion de procédure effective et la thèse de Church-Turing. Chaque notion est illustrée par une ou plusieurs applications empruntées aux domaines de la reconnaissance de motifs, la compression, la spécification des langages de programmation, la compilation, la calculabilité, l’électronique, la génération de fractales. D’autres applications comme les systèmes dynamiques discrets, les codes auto-corrrecteurs, le décodage du génôme, la linguistique y seront évoquées.

Modalités de contrôle des connaissances

• Controle continu (30%)
• Controle flash (20%)
• Controle terminal (50%)

Ressources

• Introduction à la calculabilité Wolper, InterEditions, 1991.
• Handbook of Theoretical Computer Sciences (vol.A) Ouvrage collectif, MIT Press, 1990.
• Introduction to the theory of computation Sipser, PWS publishing company, 1997.

Ressources numériques

• http://fr.wikipedia.org/wiki/Automate_fini
• http://fr.wikipedia.org/wiki/Théorie_des_langages
• http://fr.wikipedia.org/wiki/Grammaire_formelle
• http://fr.wikipedia.org/wiki/Automate_à_pile