INFO 3214

DESCRIPTION: Langages réguliers et automates à états finis et à piles. Langages libres de contexte. Hiérarchie de Chomsky. Machine de Turing. Machine universelle. Hypothèse de Church. Calculabilité et déterminisme, problèmes indécidables. Applications dans les traitements de texte et les compilateurs. RÉSULTATS D'APPRENTISSAGE : À la fin de ce cours, la personne étudiante sera en mesure de/d' : faire des démonstrations par récurrence; maîtriser le fonctionnement des automates finis non déterministes et les algorithmes associés; connaître les expressions régulières; connaître les grammaires formelles+ hors contexte et leurs applications; comprendre le fonctionnement d'une machine de Turing. PREALABLE: INFO2012 CONCOMITANT: NOTE: