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

Théorie des langages (Cours)