IFT781 - Théorie des automates et des langages formels
Présentation
Sommaire
- Cycle
- 2e cycle
- Crédits
- 3 crédits
- Faculté ou centre
- Faculté des sciences
- Répartition de la charge de travail
- 3-0-6
Cible(s) de formation
Approfondir sa connaissance des principaux outils mathématiques servant à résoudre les problèmes théoriques posés par les progrès de l'informatique.
Contenu
Automates finis, à piles, linéairement bornés. Langages réguliers, indépendants et dépendants du contexte. Relations entre ces divers types d'éléments. Problèmes décidables et indécidables. Machine de Turing. Machine de Turing universelle. Problème de l'arrêt. Classe des ensembles récursifs. Propriétés de fermeture des langages. Langages de Pétri.