Premiers éléments mathématiques et informatiques nécessaires pour les approches formelles du TAL, avec une insistance particulière sur le théorie des langages formels. Les automates, en particulier, seront examinés en détail. On s'intéressera aussi au concept d'unification, très important dans les formalismes grammaticaux modernes.

Organisation des séances

sem. date Description Liens
1 25/01 Ch1. Bases mathématiques de la TLF (1) Définitions
2 01/02 Ch1. Bases mathématiques de la TLF (2)
Exercices sur le ch. 1 		feuille n°1
3 08/02 Suite des exercices
Ch2. Automates (1) 		 
4 15/02 Ch2. Automates (2)  
5 22/02 Ch2. Automates (3)  
6 01/03 --- devoir sur table ---
7 08/03 ------ pas de séance ------
8 15/03 Ch3. Grammaires formelles (1)  
9 22/03 Ch3. Grammaires formelles (2) poly: hiérarchie de Chomsky
10 29/03 Ch3. Grammaires formelles (3)
Ch4. Théorèmes d'équivalence (1)		 poly: grammaires propres
11 05/04 Ch4. Théorèmes d'équivalence (2) poly: traduction e.r. en automate
12 12/04 Exercices sur le ch. 4 feuille n°2
13 19/04 Ch5. Recherche de motif  
 

Bibliographie

• Les bases mathématiques de la théorie des langages formels comprennent des bases en théorie des ensembles (on peut trouver ça dans beaucoup de bons manuels de maths (chercher "théorie naïve des ensembles"), voire sur wikipedia) ; et les définitions de base de la théorie des langages formels, qu'on peut trouver dans (Partee, ter Meulen & Wall 93) ou dans (Yvon & Demaille 2005).
• Les automates sont présentés au chapitre 2 de (Jurafsky & Martin 00), dans (Yvon & Demaille 2005), avec les définitions et la plupart des algorithmes de manipulation, sauf l'algorithme de MacNaughton et Yamada, plus difficile à trouver (il faut venir au cours...).
• Les bases de grammaires formelles sont présentées dans toutes les références citée ici, ainsi que dans (Aho, Lam, Sethi, Ullman 07).
• reste de la biblio à suivre selon les chapitres qui seront traités

Références

• Aho, Lam, Sethi, Ullman, Compilateurs : principes, techniques et outils, 2e édition, Pearson Éducation France, 2007. (le fameux Dragon Book).
• Daniel Jurafsky & James Martin : Speech and Language Processing, Prentice Hall, 2000. Nouvelle édition 2009.
• Barbara Partee, Alice ter Meulen & Robert E. Wall, Mathematical Methods in Linguistics, Kluwer Academic Publishers, 1993.
• Yvon, François et Akim Demaille, Théorie du Langage. Notes de cours, cours dispensé dans plusieurs établissements, 2005, 2008.