Socle commun deuxième année Licence Informatique

Théorie des langages

Course ID
UEF411
Campus
Département Informatique
Level
Licence
Semester
Semestre 3
Credit
4
Method
Cours, TD

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