Description rapide : L'automate, un outil fondamental en informatique.

Objectif : Premièrement, présenter des mécanismes permettant de tester l'appartenance d'une suite de symboles (par exemple, un programme informatique) à une famille syntaxique donnée (par exemple, un langage de programmation). Les mécanismes considérés sont les automates finis (langages reconnaissables) et les automates à pile (langages algébriques). Ensuite, présenter des mécanismes permettant de construire des langages suivant certaines spécifications. Le mécanisme étudié sera celui des grammaires algébriques. Outre la présentation de modèles théoriques des langages de programmation, cet enseignement constituera un préalable pour l'étude de la compilation.

Pré-requis : Aucun

Programme :

• Notions de base (mots, langages, ... )
• Langages reconnaissables, automates finis
• Définition, représentations
• Expressions rationnelles
• Langage reconnu par un automate 
• Propriétés de fermeture rationnelles
• Construction d'automates 
• Théorème de Kleene
• Déterminisme
• Propriétés de fermeture non rationnelles
• Minimalité
• Théorème de l'étoile
• Langages algébriques
• Automates à pile, langages reconnus
• Grammaires algébriques, langages engendrés
• Langages algébriques déterministes
• Ambiguté

Bibliographie :

• <>Patrice Séébold, Théorie des automates - Méthodes et exercices corrigés, Vuibert Informatique, Collection Passeport pour l'informatique, Paris, 1999.
• <>Jean-Michel Autebert, Théorie des langages et des automates, Masson, Collection Manuels Informatiques Masson, Paris, 1994.