l'ÉITIRechercheNouvelles HREF=RépertoiresRessourcesGénie/EngineeringUd'O/UofOSITESearchNewsDirectoriesResourcesSITE

CSI 3504 Introduction aux langages formels
Hiver 2017

(3 heures de cours par semaine, 3 crédits)
Langages rationnels, automates d'états finis, graphes de transition et théorème de Kleene. Machines séquentielles. Langages non contextuels, arbres de dérivations, grammaires de forme normale, automates à pile, déterminisme. Décidabilité. Langages récursivement dénombrables, machines de Turing, le problème de terminaison. Préalables: CSI 2501 ou MAT 2543.

Plan de cours

Professeur

Heures de bureau

Horaire de cours

Manuel de cours

Evaluation

Devoirs

Examens

Droit d'auteur

Sites web supplémentaires

Plan approximatif des cours:

Sujet Lecture Notes de cours Date
Introduction, langages, définitions récursives chapitres 1, 2, 3 chapitres 1 et 2,
chapitre 3
10-13 janvier
Expressions rationnelles chapitre 4 chapitre 4 13-17 janvier
Automate finis, graphes de transition chapitres 5, 6 chapitre 5,
chapitre 6
17-24 janvier
Théorème de Kleene, nondéterminisme chapitre 7 chapitre 7 24 janvier-14 février
Machines séquentielles, langages rationnels chapitres 8, 9 chapitre 8,
chapitre 9
14-17 février
Langages non-rationnels, décidabilité chapitres 10 (pages 187-196), 11 chapitre 10,
chapitre 11
17 février-3 mars
Grammaires non contextuelles, formats des grammaires chapitres 12, 13 chapitre 12,
chapitre 13
3-14 mars
Automates à pile, Grammaires non contextuelles = automates à pile chapitres 14, 15 (pages 318-327) chapitre 14,
chapitre 15
14-21 mars
Langages contextuels, Langages non contextuels chapitres 16, 17 chapitre 16,
chapitre 17
24 mars- 
Décidabilité, analyse syntaxique, Machines de Turing chapitres 18 (pages 402-410 et 415-423), 19    
Langages récursivement dénombrables, révision chapitre 23