Théorie des langages

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. ‘epré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
4. Propriétés d’une grammaire régulière
5. Transformations d’une grammaire
6. Grammaire réduite
7. Grammaire propre
8. Elimination des récursivités à gauche
9. 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

1. Wolper. Introduction à la calculabilité. 2006, Dunod.
2. Séébold. Théorie des automates. 2009, Vuibert.
3. 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