Ects : 5
Volume horaire : 51

Description du contenu de l'enseignement :

Le but de ce cours est d'acquérir les bases des langages formels :

1. Mots et langages, lemme d'Arden (équations linéaires sur les langages)
2. Automates finis et langages rationnels : équivalence entre langages reconnus par automates finis et langages rationnels. Algorithmes de déterminisation et de minimisation.
3. Grammaires et langages algébriques. Transformation de grammaires, ambiguïté, équivalence avec les langages reconnus par automates à pile.
4. Brève introduction à la calculabilité et aux machines de Turing

La principale application de ce cours sera aux premières étapes de la compilation : analyse lexicale et syntaxique, avec utilisation des outils Flex et Bison en TP.

Compétence à acquérir :

• Être capable de reconnaître et de définir des langages rationnels et algébriques, et de manipuler les structures qui les représentent
• Pouvoir écrire un analyseur syntaxique simple pour analyser des données structurées

Bibliographie, lectures recommandées

• Jean-Michel Autebert, Théorie des langages et des automates, 1994, Masson

En savoir plus sur le cours