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 20/01 Ch1. Bases mathématiques de la TLF (1) Définitions
2 27/01 ---- Séance annulée ----
3 03/02 Ch1. Bases mathématiques de la TLF (2)
Exercices sur le ch. 1 		feuille n°1 (nouvelle)
4 10/02 Ch2. Automates (1) Voir le polycopié proposé comme synthèse aux étudiants de M1
5 17/02 Ch2. Automates (2)
6 24/02 Ch2. Automates (3)
Exercices sur le ch. 2 		feuille n°2
7 03/03 ---- Devoir sur table ----
8 10/03 Ch3. Grammaires formelles (1)  
9 17/03 Ch3. Grammaires formelles (2) poly: exemples
10 24/03 Ch4. Théorèmes d'équivalence (2)  
11 31/03 Ch4. Théorèmes d'équivalence (3)
Exercices sur les ch. 3 & 4 		feuille n°3
12 07/04 Ch5. Recherche de motif poly: parcours d'arbre
13 14/04 Ch5. Recherche de motif (2)
Ch6. Transducteurs 		 
 

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.