Eugène Asarin, mail : Professeur à l'Université Joseph Fourier à l'UFR IMA, Laboratoire VERIMAG, Chargé de cours et de TD (G1)
Saddek Bensalem, mail : Professeur à l'Université Joseph Fourier à l'UFR IMA, Laboratoire VERIMAG, Chargé de TD (G2)
Iulian Ober, mail : Post-doctorant à VERIMAG, Chargé de TD (G3)
Pour joindre toute l'équipe
Cours : vendredi , 8h30 -10h00, salle 001 à l'ISTG
TD :
Groupe 1: mercredi, 16h15-17h45, Salle C02 à l'UFR IMA (sur le campus)
Groupe 2: vendredi, 13h30-15h00, Salle 125 à l'ISTG
Groupe 3: lundi, 17h -18h30, Salle 123 à l'ISTGExamen : Mercredi 8/01 9h-12h à la Faculté de Médecine Amphi Inférieur NORD et Amphi Supérieur NORD
NEW: Examen du 8/01/2003 sujet, corrigé
Quick du 12/12/2002 avec corrigé pdf
Automates et langages : quelques algorithmes: pdf
(un petit bug est corrigé: section 4.2.2,
l'automate pour f*)
Pages du même cours : 2000 ; 2001 (printemps); 2001 (automne)
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)
Examen corrigé de 2001 (automne) : Postscript, pdf
Semaine 1 : Introduction
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 des automates déterministesFeuille de TD1
Semaine 2 Automates non-déterministes avec epsilon-transitions
TA: Automates non-déterministes finis avec epsilon-transitions. Calculs et langages acceptés des automates non-déterministes. Théorème de déterminisation. Algorithme de déterminisation - l'idée.
Feuille de TD2
Semaine 3 Démonstration de théorème de déterminisation. Successeurs. Expressions régulières.
TA: Sucesseurs ( y compris la définition inductive). Algorithme de déterminisation - les détails. 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 des expressions régulières et des 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 Langages réguliers (TL).
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.
Expression régulières étendues
Algorithmes de décision pour les langages réguliers: appartenance, langage vide, langage fini, inclusion de langages, égalité de langages.
Semaine 7 Preuve de non-régularité (TL).
Lemme de gonflement. Le langage {anbn} n'est pas régulier (preuve).
Feuille de TD7-8. Corrigé d'un exercice sur Pumping Lemma (an 2000)
Semaine 8 Minimisation. Application des automates. (TA)
Algorithme de minimisation.
Applications: recherche de motif et analyse lexicale
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.
Feuille de TD9
Semaine 10 Langages hors contexte. (TL)
Langages HC. BNF. Dérivation, arbre de dérivation. Problème de l'analyse syntaxique. Ambigüité.
Propriétés de fermeture par concaténation, itération, union. Non-fermeture par intersection et complément.
Feuille de TD10
Semaine 11 Langages hors contexte et automates à pile. (TL)
Algorithme de décision de l'appartenance d'un mot à un langage hors contexte.
Notion d'un automate à pile et de son langage accepté.
Théorème : la classe des langages acceptés par les automates à pile = langages HC (sans preuve)
N'hésitez pas de nous envoyer vos commentaires, solutions des exercices, demandes d'information sur le contenu de cours. On apprécierait beaucoup les notes de cours (en tex, html ou word).