Aller au contenu

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.