LI 032 : Langages formels et automates

On présentera dans ce cours les bases avancées de la théorie des langages formels, aussi bien du point de vue mathématique que des points de vue informatique et linguistique. On y évoquera : les machines à états finis (machine de Turing, automates...) ; les langages réguliers ; les grammaires formelles et la hiérarchie de Chomsky ; les notions de décidabilité, énumérabilité.

Ce cours constitue une préparation pour le cours du second semestre, intitulé « parsing », décrit sur la page suivante.
Polycopié pour le chapitre « traduction dirigée par la syntaxe », format PDF.

Liens vers les cours des années précédentes : 2002/03 2001/02

Emploi du temps

 LI032 (S1)
Horaires : Jeudi
12:00 à 14:00
Salle : RC2
Premier cours Jeudi 02 Octobre

Modalités de contrôle

  • Contrôle continu
    Un DST (40%) et un partiel en fin de semestre (60%)
  • Contrôle terminal
    Un examen en fin de semestre (100%)

Plan indicatif

    Introduction & Rappels
  • (09/10) (PA) Rappels : expressions rationnelles, automates
  • (16/10) (PA) Rappels : automates, grammaires
    Langages rationnels
  • (23/10) (PA) Ch2: Automates (1)
  • (30/10) (PA) Ch2: Automates (2)
  • (06/11) (PA) Ch2: Automates (3)
  • (13/11) (PA) Ch3: Grammaires régulières
  • (20/11) (PA) Ch4: Introduction à lex
     
  • (27/11) (PA) Partiel
     
    Langages hors-contexte
  • (04/12) (AN) Automates à pile
  • (11/12) (AN) Grammaires hors contexte (1)
  • (18/12) (AN) Grammaires hors contexte (2)
    Machines de Turing
  • (08/01) (PA) Machines de Turing
  • (15/01) (PA) Langages de type 0 & 1, décidabilité

Contrôles

    LI032
  • Devoir sur table n° 1 : jeudi 27 novembre horaire et salle habituels (1h30 d'épreuve, sans documents)
  • Examen final (pour tous les étudiants) :
    Jeudi 22 janvier 2004, de 8h30 à 11h30, Amphi 55A.


Bibliographie

  • A. Aho, R. Sethi & J. Ullman : Compilateurs, principes, techniques et outils, Interéditions, 1989.
  • J.-M. Autebert : Langages algébriques, Masson, 1987.
  • D. Jurafsky & J. Martin : Speech and Language Processing, Prentice Hall, 2000.
  • A. Aho & J. Ullman : The Theory of Parsing, Translation, and Compiling, Prentice Hall, 1972.
     
  • A. Aho & J. Ullman : Concepts fondamentaux de l'informatique, Dunod, 1992.
http://www.linguist.jussieu.fr/~amsili/Ens04/LI032.html Last modified: Wed Mar 17 10:24:52 CET 2004 Ma maison-page