Site officiel du LSV

Cours Langages formels

Cours du 11/03 et 12/03: Grammaires générales (type 0), contextuelles (type 1), algébriques (type 2), linéaires, hiérarchie de Chomsky.
Cours du 19/03: Arbres de dérivation, ambigüité, exemples. Théorème de Bar-Hillel, Perles, Shamir. Lemme d'Ogden. Applications.
Cours du 26/03: Formes normales preuves et algorithmes. Problème du mot Algorithme de Cocke, Younger et Kasami. Problèmes indécidables preuves.
Cours du 02/04: Forme normale de Greibach (exemples et preuves). Automates à pile: définitions, exemples, lemme fondamental, acceptation généralisée, équivalence avec les grammaires algébriques (exemples et preuves).
Cours du 23/04: Configurations accessibles d'un automate à pile, calculs d'accessibilité. Voir les notes de cours sur les automates à pile.
Cours du 30/04: Automates à pile déterministes, exemples, blocages, complémentaire. Voir les notes de cours sur les automates à pile.