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.

À 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.

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.

À l'entrée de cette UE, un(e) étudiant(e) devrait :
- connaître les rudiments de la théorie des ensembles et de la récursion (cf. Fondement du calcul et du raisonnement en S2),
- connaître des notions en algèbre et analyse (cf. Algèbre 2 en S2 et Analyse 2 en S3),
- connaître des notions de la logique classique et les différents mode de raisonnement (cf. Logique et Programmation Logique en S3),
- connaître des notions sur le graphes (cf. Graphes en S5).