Description

Cette unité d'enseignement pose les fondements de la théorie des langages. Son objectif premier est la compréhension de certains mécanismes inhérents à la conception des langages de programmation et à une introduction à la théorie de la calculabilité. Ses applications peuvent néanmoins s'étendre à d'autres domaines scientifiques.
Le plan du cours est le suivant : après l'introduction d'un certain nombre d'outils formels en relation avec les notions de langage formel, nous présenterons en détails la classe des langages rationnels et la classe des langages algébriques. Nous présenterons ainsi différentes notions correspondant à la classe des langages rationnels : les expressions rationnelles ; les automates d'états finis (déterministes et non déterministes) ; la déterminisation des automates ; des propriétés de stabilité de la classe des langages rationnels ; le lemme de l’Étoile puis la minimisation des automates. Nous présenterons ensuite différentes notions correspondant à la classe des langages algébriques : les grammaires algébriques ; les automates à pile ; les propriétés de stabilité de la classe des langages algébriques ; le lemme de la double Étoile puis les équivalences automates-grammaires.
Ce cours se terminera par une introduction aux machines de Turing qui sont des « ultimes » généralisations de la notion d'automate.

Compétences visées

À l'issue de cette UE un(e) étudiant(e) devrait :
- savoir manipuler les expressions rationnelles et les automates déterministes/non-déterministes,
- comprendre le lien entre les expressions rationnelles et les automates,
- savoir manipuler les grammaires algébriques et les automates à pile,
- comprendre le lien entre les grammaires algébriques et les automates à pile,
- comprendre plus généralement le lien entre les outils permettant de générer les mots d'un langage et les machines permettant la reconnaissance des mots de ce même langage,
- savoir utiliser des outils permettant de classifier les langages et avoir une bonne compréhension de la hiérarchie de différentes classes de langages.

Bibliographie

Références :
- [L&P 98] Harry R. Lewis & Christos H. Papadimitriou. « Elements of the theory of computation » Prentice Hall, Inc.
- [Aut 97] J.-M. Autebert. « Théorie des langages et des automates ». Masson.