CSI 3504

Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
CSI 3504

CSI 3504 Introduction aux langages formels
Hiver 2003

(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: MAT 1761, MAT2743, ou MAT 2543.

Professeur

Manuel de cours

Introduction to Computer Theory

Plan approximatif des cours:

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