Enseignement de théorie des langages

• 3^ème année de Licence d'informatique
  Le cours de TL traite principalement des grammaires ainsi que des langages rationnels et algébriques et de leurs reconnaisseurs.
  
  Le chapitrage du cours est le suivant
  • Introduction
  • Ce que l'on appelle langage
  • Théorie des langages et calculabilité
  • Les mots
  • Les langages
  • Les grammaires
  • Les définitions de bases
  • Hiérarchie de langages et types de grammaires
  • Les automates finis
  • Présentation des automates finis non-déterministes (AFN)
  • Automates non déterministes avec epsilon-transitions
  • Les Automates finis déterministes
  • Langages rationnels
  • Conversion d'expression rationnelle en automate fini
  • Théorème de Kleene et algorithme de McNaughton-Yamada
  • Langages non rationnels et lemme de la pompe
  • L'automate minimal
  • Les grammaires algébriques
  • Arbres de dérivation et ambiguité
  • Simplification de grammaires algébriques
  • Les propriétés d'itération pour les langages algébriques
  • Les automates à piles
  
  
  Les TD de théorie des langages sont assurés par M. Léonard .