Matière : Théorie des langages
Unité d’enseignement fondamentale : UEF1
Crédits : 5
Coefficient : 2
Objectifs de l’enseignement : comprendre la théorie et les outils de la théorie des langages
Connaissances préalables recommandées : Connaissances de base en mathématiques et en informatique
Contenu de la matière :
Chapitre 1 : Introduction (objectifs …)
Chapitre 2 : Alphabets, Mots, Langages
Chapitre 3 : Grammaires
1. Définitions
2. Dérivation et langage engendré
3. Arbre de dérivation
4. Hiérarchie de Chomsky
Chapitre 4: Automates d’états finis (AEF)
1. AEF déterministes
2. Représentations d’un automate
3. Automates équivalents et complets
4. AEF non déterministes (déterminisation)
5. Automates et langages réguliers (transformations et propriétés))
Chapitre 5: Expressions Régulières
1. Définitions
2. Théorème de Kleene
3. Lemme de l’étoile
Chapitre 6: Minimisation d’un AEF
Chapitre 7: Langages Algébriques
1. Propriétés d’une grammaire régulière
2. Transformations d’une grammaire
3. Grammaire réduite
4. Grammaire propre
5. Elimination des récursivités à gauche
6. Formes normales
Chapitre 8: Automates à Piles
1. Définition
2. Configuration, transition et calcul
3. Critères d’acceptation
4. Automates à piles déterministes
Chapitre 9: Machine de Turing
1. Définition
2. Configuration, transition et calcul
3. Acceptation
Mode d’évaluation : Examen (60%) , contrôle continu (40%)
Références
- P. Wolper. Introduction à la calculabilité. 2006, Dunod.
- P. Séébold. Théorie des automates. 2009, Vuibert.
- J.M. Autebert Théorie des langages et des automates. 1994, Masson.
- J. Hopcroft, J. Ullman. Introduction to Automata Theory, Languages and Compilation 1979, Addison-Wesley