IFT781 - Théorie des automates et des langages formels

programmes offrant cette activité pédagogique (cours)

Doctorat en informatique

Maîtrise en informatique

Sommaire

Cycle
2e cycle
Crédits
3 crédits
Durée
1 trimestre
Faculté/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.