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
