Eugène Asarin : Professeur à l'Université Joseph Fourier à l'UFR IMA, Laboratoire VERIMAG, Chargé de cours et de TD
Magali Lavandier : Chargée de TD
Pour joindre toute l'équipe
Cours : Mardi après-midi , 17h -18h30, salle 101 à l'ISTG
TD :
Groupe 1: vendredi, 16h15-17h45, Salle 313 à l'ISTG
Groupe 2: jeudi, 11h30-13h, Salle F213 à l'IMA (sur le campus)
J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
Cl.Benzaken, Systèmes Formels, Masson, 1991.
Semaine 1 : Introduction du module
Automates comme le modèle de base de systèmes informatiques.
Théorie de langages (TL): alphabet, mot, langage.
Théorie d'automates (TA): automate déterministe.Feuille de TD1
Semaine 2: Automates deterministes et indeterministes
TA: calculs et langages acceptés d'automates déterministes. Automates indéterministes, leurs calculs et langages. Théorème de déterminisation.
Feuille de TD2 TA: élimination de epsilon-transitions.
Semaine 3: Quelques démonstrations, algorithmes et programmes
TA: Algorithme de déterminisation et la preuve de sa correction. "Epsilon-automates" et l'algorithme d'élimination d'epsilon-transitions.
Feuille de TD3 : un peu de programmation.
Semaine 4: Expressions régulières, théorème de Kleene
TL: opérations sur les mots et les langages. Expressions régulières et leur sémantyque. quelques identités.
TL+TA. Théorème d'equivalence d'expressions régulières et d'automates finis (Kleene): énoncé, algorithme de synthèse de l'automate pour un langage défini par une expression régulière.
TL : Equations sur les langages et leurs solutions.
Feuille de TD4 : expressions régulières, équations et systèmes d'équations
Semaine 5 : Langages réguliers
TL+TA. Théorème de Kleene (suite et fin): méthode pour trouver l'expression régulière à partir d'un automate (en utilisant les équations)
TL : Caractérisations différentes de langages réguliers. Propriétés de fermeture de la classe de langages réguliers - opérations sur les langages et sur les automates
Feuille de TD5 : de l'automate vers l'expression régulière, opérations sur les langages
Semaine 6 : Repos et révisions
Pas de cours. TD: révisions.
Semaine 7 : Langages réguliers et non-réguliers
TL+TA : Propriétés de fermeture de la classe de langages réguliers - opérations sur les langages et sur les automates - suite et fin. Produit des automates et son sens informatique. Coût des opérations sur les automates.
Lemme de gonflement. Langages non-réguliers et démostration de leur non-régularité
Feuille de TD7 : opérations sur les langages, produits des automates, langages non-réguliers.
Semaine 8 : Minimisation
TA : Construction de l'automate minimal. Un algorithme plus concret.
Feuille de TD8 : minimisation.
Semaine 9 : Myhill-Nerode et quelques algorithmes
TA : Théorème de Myhill-Nerode
Bilan sur les langages réguliers: représentations, opérations, algorithmes de décision.
TD9 - une interrogation écrite : sujet, corrigé de l'exercice 4
Semaine 10 : Grammaires
TL : Les grammaires et leurs langages engendrés. Types de grammaires : hiérarchie de Chomsky.
TL+TA: Langages réguliers = langages de grammaires régulières
Feuille de TD10 : grammaires.
Semaine 11: Induction
Définition d'un ensemble par un schéma d'induction.
Feuille de TD11 : encore une fois - lemme de gonflement. Schémas d'induction, dérivation, arbre de derivation, ambiguité.
Semaine 12: Induction
Dérivation, arbre de derivation. Ambiguité. Définition d'une fonction par récursion structurelle. Problèmes de consistance et complétude. Raisonnement par induction structurelle. Quelques mots sur le "principe d'oignon".
Feuille de TD12
N'hésitez pas de nous envoyer vos commentaires, solutions des exercices, demandes d'information sur le contenu de cours.