Revenir à Maîtrise d’ informatique

Théorie des langages

Objectifs

Donner les notions de base sur les langages algébriques. On insiste sur l’aspect « système d’équations » et « définition récursive », dans la perspective de la généralisation à d’autres types de définitions récursives, en sémantique des langages de programmation en particulier.

Programme

  • Rappels et compléments sur les langages rationnels : langages, automates finis et expressions rationnelles; théorème de Kleene; automate minimal, automates finis avec sortie, décodage pour un code préfixe.
  • Les langages algébriques : grammaires, arbres de dérivation et théorème des dérivations gauches; systèmes d’équation; transformations de grammaires préservant le langage engendré, propriétés de fermeture; langages non algébriques, preuves de propriétés des langages algébriques; décidabilité de problèmes relatifs aux langages et grammaires algébriques; algorithmes itératifs sur les grammaires.
  • Schémas de programmes itératifs : trace d’un schéma itératif et relation avec les automates finis, preuves d’équivalence de schémas itératifs.

Bibliographie

  • Introduction to formal language theory, M.A. Harrison, [Addison-Wesley]
  • Mathématiques pour l’informatique, A. Arnold et I. Guessarian, [Masson]
  • Théorie des langages et des automates, J.M. Autebert, [Masson]
  • Le langage des machines, R. Floyd, R. Biegel, [InternationalThomsonPublishing]

Annales d’examen

Travaux dirigés

Devoirs