Partager cette page :
Discipline(s) : Infomatique et télécommunications

LF : langages formels et calculabilité

Semestre Semestre 1
Type Obligatoire
Nature UE
Crédits ECTS 6
Volume horaire total 40
Volume horaire CM 20
Volume horaire TD 20

Responsables

Gilles Lesventes

Pré-requis

Mathématiques élémentaires (démonstrations, etc.).
Un prérequis en théorie des automates finis est apprécié mais n’est pas obligatoire (la théorie des automates est revisitée en début de cours).

Objectifs

Acquérir une bonne intuition sur les capacités d'expression des différents modèles. Savoir mettre en œuvre les modèles et les algorithmes associés (déterminisation, minimisation, etc.). Le cours et les TD associés sont aussi l'occasion d'acquérir ou de renforcer de bons réflexes de rigueur dans les raisonnements.

Contenu

Description du cours

L'objectif du cours est d'étudier conjointement deux des piliers fondamentaux de l'informatique : les notions de langage formel, et de machine, appréhendée en tant que modèle de calcul. Le but ultime est de répondre à la question : qu'est-ce qui est calculable par une machine ? On s'intéresse donc aux différentes classes de langages (rationnels, algébriques, récursifs, etc.), et aux dispositifs permettant de les reconnaître (automates finis, automates à pile, machines de Turing, etc.) ou de les générer (expressions rationnelles, grammaires). Le cours s'attache à montrer le pouvoir d'expression de ces différentes classes, et à mettre en lumière quelque liens avec les domaines d'applications de ces fondements (algèbre, logique, compilation, etc.).

Programme

A – Langages rationnels 
1. Expressions rationnelles
2. Automates finis
3. Théorème de Kleene
4. Automates déterministes complets.
5. Type abstrait « langage rationnel » : application à l’arithmétique de Presburger.
6. Automate minimal
B – Langages algébriques
1. Grammaires algébriques
2. Problème du mot
3. Automates à pile
C – Calculabilité
4. Machines de Turing
5. Théories des fonctions récursives
6. Décidabilité et indécidabilité

Références


Bibliographie

J.-M. Autebert, Théorie des langages et des automates, Masson, 1994.
 
Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008.
 
John E. Hopcroft, Rajeev Motwani, et Jeffrey D. Ullman, Introduction to
Automata Theory, Languages, and Computation, Prentice Hall, 2007.
 
J. Sakarovitch, Eléments de théorie des Automates, Vuibert, 2003.
 
Pierre Wolper, Introduction à la calculabilité, Dunod, 2006.
 
Michael Sipser. Introduction to the Theory of Computation. Boston : Thomson Course Technology, 2006.

Mise à jour le 29 avril 2021