RESUME COURS :
- Objectifs d'apprentissage: Notions théoriques sur les langages formels, techniques de preuve, principe de l'analyse syntaxique ascendante, notions élémentaires de calculabilité.
- Continuité: Le cours de LF approfondi et place dans leur contexte théorique les fondamentaux abordés au cours de L2/PIL (automate d'états fini, expressions rationnelles). Il développe ensuite les concepts nécessaire a un cours de compilation
- Description: le cours se développe comme suit:
1-Automates finis : non déterminisme, expression rationnelle, preuve du théorème de Kleene (système d'équations associé à un automate), minimisation, résiduels, construction directe de l'automate minimal, lemme de l'étoile, pompage, propriétés de clôture, lien avec l'analyse lexicale.
2-Grammaires : hiérarchie de Chomsky, grammaire régulière, grammaires hors contexte.
Lemme de la double étoile pour les langages algébriques, propriétés de clôture.
Illustration avec des grammaire de vrai langage de programmation.
3-Automates à pile : fonctionnement non-déterministe, blocage, terminaison, lien avec les langages algébrique.
4-Analyse syntaxique : analyse LR, calcul des tables d'analyse ascendante SLR(1), gestion des conflits, le cas LALR.
5-Machines de Turing : définition, langage/problèmes indécidables. Le problème de l'arrêt.
Introduction aux classes de complexité, P, NP, problème NP-complet.
- Enseignant: Frédéric Gruau
- Enseignant: Thomas Soullard