Introduction aux formalismes utilisés pour la définition de la syntaxe des langages informatiques, étude de leurs propriétés, et des outils servant à les étudier.

I - Introduction à la théorie des langages
Vocabulaire, chaîne, concaténation, opérations sur les langages
II - Langages réguliers
Automates finis, déterminisation, minimisation
Expressions régulières, équivalence des deux représentations
Fermeture et existence de langages non réguliers
III - Grammaires, hiérarchie de Chomsky
Manipulations de grammaires
Arbres de dérivation, ambiguïté
Preuves sur grammaires

Néant.

P. Berlioux, M. Echenim, M. Lévy : Théorie des langages, polycopié Ensimag
J.E. Hopcroft, R. Motwani, J.D. Ullman : Introduction to Automata Theory, Languages, and Computation, 3/E, Addison-Wesley, 2006

Deux examens écrits de 2 h.

N1=(E1a+E1b)/2
N2=E2