Module « Théorie des langages »
Volume horaire
- 32 heures de cours magistral.
- 32 heures de travaux dirigés.
Description du module
Le cours de théorie des langages traite principalement des grammaires ainsi que des langages rationnels et algébriques et de leurs reconnaisseurs.
- Introduction : ce que l'on appelle langage, théorie des langages et calculabilité, mots, langages.
- Les grammaires : 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, 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, automate minimal.
- Les grammaires algébriques : arbres de dérivation et ambigüité, simplification de grammaires algébriques, propriétés d'itération pour les langages algébriques.
- Les automates à piles.