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.