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
Catalin Dima: Thésard à l'Université Joseph Fourier, Laboratoire VERIMAG, Chargé de TD
Pour joindre toute l'équipe
Cours : Jeudi , 9h45 -11h15, salle 101 à l'ISTG
TD :
Groupe 1: lundi, 13h30-15h00, Salle 313 à l'ISTG
Groupe 2: mardi, 17h00-18h30, Salle 013 à l'ISTG
Groupe 3: lundi, 15h15-16h45, Salle F212 à 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.
P. Wolper. Introduction à la calculabilité - Paris : InterEditions, 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)
Semaine 1 (jeudi 25/01/01 - mercredi 31/01/01): 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. Calculs et langages acceptés d'automates déterministes.Feuille de TD1
Semaine 2 (jeudi 1/02/01 - mercredi 7/02/01): Automates non-déterministes
TA: automate non-déterministe fini. Calculs et langages acceptés d'automates no-déterministes. Outil: la notion de successeur d'un état et d'un ensemble des états. Théorème de déterminisation. Algorithme de déterminisation et la preuve de sa correction.
Feuille de TD2
Semaine 3 (jeudi 8/02/01 - mercredi 21/02/01): Epsilon. Expressions régulières
TA: automate avec epsilon-transitions. Théorème d'élimination d'epsilon-transitions. Algorithme d'élimination et l'idée de preuve de sa correction.
TL: Opérations sur les langages. Expressions régulières et leur sens (langage dénoté)
Feuille de TD3
Semaine 4 (jeudi 22/02/01 - mercredi 28/02/01): 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
Semaines 5-6 (jeudi 01/03/01 - mercredi 14/03/01): Langages réguliers.
3h de cours le 01/03, pas de cours le 08/03
TA+TL : Théorème de Kleene - fin de preuve : algorithme de solution d'un système d'équations par élimination Gaussienne.
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.
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.
Feuille de TD5
Feuile de TD6
Semaine 7 (jeudi 15/03/01 - mercredi 21/03/01): Minimisation.
TL: Opération sur les languages : quotient (dérivée)
TA: Minimisation d'un automate déterministe
Feuille de TD7
Semaine 8 (jeudi 22/03/01 - mercredi 28/03/01): Myhill-Nerode.
TL+TA: Théorème de Myhill-Nérode
TA: Quelques mots sur les applications: analyse lexical, recherche d'un motif
TD: révisions
Semaine 9(jeudi 29/03/01 - mercredi 04/04/01): Quick et sa correction.
Semaine 10-11(jeudi 05/04/01 - mardi 24/04/01): 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 TD10,
Semaine 12 (mercredi 25/04/01 - vendredi 27/04/01): Langages hors contexte
TL: Langages HC. Propriétés de fermeture sous concaténation, itération, union. Algorithmes relatives aux langages HC: tests d'appartenance, langage vide. Indécidabilité de problèmes de langage universel, inclusion, égalité.
TA: Automates à pile et leur langages. Théorème: langages HC= langages des automates à pile (sans preuve).
Feuille de TD11
N'hésitez pas de nous envoyer vos commentaires, solutions des exercices, demandes d'information sur le contenu de cours.