Eugène Asarin : Professeur à l'Université Joseph Fourier à l'UFR IMA, Laboratoire VERIMAG, Chargé de cours et de TD
Yassine Lakhnech : Professeur à l'Université Joseph Fourier à l'UFR IMA, Laboratoire VERIMAG, Chargé de TD
Yasmina Abdeddaim : Étudiante en thèse à l'Université Joseph Fourier, Laboratoire VERIMAG, Chargé de TD
Pour joindre toute l'équipe
Cours : vendredi , 8h30 -10h00, salle 001 à l'ISTG
TD :
Groupe 1: lundi, 17h00-18h30, Salle 117 à l'ISTG
Groupe 2: mardi, 13h30-15h00, Salle F117 à l'UFR IMA (sur le campus)
Groupe 3: vendredi, 15h15-16h45, Salle F118 à l'UFR IMA
J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979
P. Wolper. Introduction à la calculabilité - Paris : InterEditions, 1991.
Cl.Benzaken, Systèmes Formels, Masson, 1991.
Page du même cours d'année 2000
Sujet de l'examen de l'an 2000 (exo 5 n'est pas dans le programme de cette année)
Corrigé d'un exercice sur Pumping Lemma (an 2000)
Page du même cours d'année 2001 (printemps)
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 fini.Feuille de TD1
Semaine 2 Automates non-déterministes avec epsilon-transitions
TA: Calculs et langages acceptés d'automates déterministes.
Automate non-déterministe fini avec epsilon-transitions. Calculs et langages acceptés d'automates no-déterministes. Théorème de déterminisation. Algorithme de déterminisation - l'idée.
Feuille de TD2
Semaine 3 Démonstration. Successeurs. Expressions régulières.
TA: Sucesseurs ( y compris la définition inductive). Algorithme de déterminisation - les détails. Idée de preuve du théorème de déterminisation.
TL: Opérations sur les langages. Expression régulières et leurs langages.
Feuille de TD3
Semaine 4 Théorème de Kleene
TA+TL : Théorème d'equivalence d'expressions régulières et d'automates finis (Kleene). Opération sur les automates: choix, composition séquentielle, itération. Equations sur les langages et leurs solutions.
Feuille de TD4
Semaine 5 Langages réguliers.
Langages réguliers : les représentation différentes.
Propriétés de ferméture des langages réguliers par rapport aux opérations de concaténation, itération, union (déjà vus - semaine 4), complémentation, intersection. Automate produit.
Feuille de TD5
Semaine 6 Langages réguliers et non-réguliers.
Expressions régulières étendues - encore une représentation.
Algorithmes relatives aux langages réguliers: tests d'appartenance, langage vide, langage universel, inclusion, égalité.
Langages réguliers et non-réguliers. Lemme de gonflement (pumping lemma). Preuve de non-régularité du langage anbn.
Feuile de TD6
Semaine 7 Minimisation.
TL: Opération sur les languages : quotient (dérivée)
TA: Minimisation d'un automate déterministe
Feuille de TD7 (sur le Pumping Lemma)
Semaine 8
Feuille de TD8 (sur la minimisation)
Semaine 9 Grammaires
TL: Les grammaires et leurs langages engendrés. Types de grammaires : hiérarchie de Chomsky. Théorème: Langages réguliers = langages de grammaires régulières.
Grammaires hors contexte: dérivation, arbre de dérivation. BNF. Problème de l'analyse syntaxique.
Feuille de TD9
N'hésitez pas de nous envoyer vos commentaires, solutions des exercices, demandes d'information sur le contenu de cours.