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.
Professeur
-
Dr. Amy Felty
SITE 5-068
afelty@eecs.uottawa.ca
Manuel de cours
- Introduction to Computer Theory, Daniel Cohen, Wiley, 2ème édition.
Plan approximatif des cours:
| Sujet | Lecture |
|---|---|
| Introduction, langages, définitions récursives | chapitres 1, 2, 3 |
| Expressions rationnelles | chapitre 4 |
| Automate finis, graphes de transition | chapitres 5, 6 |
| Théorème de Kleene, nondéterminisme | chapitre 7 |
| Machines séquentielles, langages rationnels | chapitres 8, 9 |
| Langages non-rationnels, décidabilité | chapitres 10 (pages 187-196), 11 |
| Grammaires non contextuelles, formats des grammaires | chapitres 12, 13 |
| Automates à pile, Grammaires non contextuelles = automates à pile | chapitres 14, 15 (pages 318-327) |
| Langages contextuels, Langages non contextuels | chapitres 16, 17 |
| 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 |
