Langages formels et calculabilité

Ce cours propose une introduction à la théorie des langages formels et à la
théorie du calcul. Nous débutons par la distinction entre langages naturels
et langages formels. Les éléments constitutifs d’un langage formel (symbole,
alphabet, mot) sont introduits, ainsi que les opérateurs (union, produit, étoile
de Kleene) et propriétés associés. La notion d’automate est liée à celle d’une
machine permettant de reconnaître les mots d’un langage. Automates à états
finis déterministes et non déterministes sont alors distingués et les processus de
déterminisation et de minimisation étudiés. Les différents types de grammaire
générative proposés par Noam Chomsky sont exposés en tant qu’ensembles de
règles permettant de générer les mots d’un langage. Il est ensuite montré que les
limites des automates à états finis peuvent être dépassées grâce aux automates
à piles. Enfin, les machines de Turing sont introduites en tant qu’instruments
de manipulation de symboles extrêmement basiques qui, malgré leur simplicité,
peuvent être adaptées pour simuler la logique d’un ordinateur

-objectif 1 : Développer la compréhension des notions de mots, langages

-objectif 2 : Introduire et étudier les automates de calcul abstraits (tels que
les machines à états finis, les machines à piles, et les machines de Turing)

-objectif 3 : Développer la compréhension des différents types de grammaires
formelles

- objectif 4 : Comprendre les relations entre ces différents automates, les
grammaires formelles et les langages.

aucun pré-requis pour ce cours d’introduction à la théorie des langages formels
et à la théorie du calcul

Des travaux dirigés permettent de mettre en œuvre les notions vues en cours.

Compréhension des principes régissant la conception et l’analyse des langages
formels, les grammaires associées, les différents types d’automate, et les machines
de Turing