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.
|
Organisation des séances
sem. | date | Description | Liens |
01 | 17/01/2017 | Ch1. Rappels mathématiques | Polycopié: définitions |
02 | 24/01/2017 | Ch1. Rappels mathématiques
Exercices (th. des ensembles, langages formels) |
feuille n°1 |
03 | 31/01/2017 | Ch2. Automates | |
04 | 07/02/2017 | Pas de séance | |
05 | 14/02/2017 | Ch2. Automates | Polycopié: exemples |
06 | 21/02/2017 |
Ch2. Automates
Ch3. Grammaires formelles |
Polycopié: exemples |
07 | 28/02/2017 | Devoir sur table | |
08 | 07/03/2017 | Ch3. Grammaires formelles | |
09 | 14/03/2017 | Ch3. Grammaires formelles | |
10 | 21/03/2017 |
Exercices (grammaires)
Ch4. Théorèmes d'équivalence |
feuille n°2 poly: ER → AFnD |
11 | 28/03/2017 |
Ch4. Théorèmes d'équivalence
Exercices (grammaires et automates) |
feuille n°3 |
12 | 18/04/2017 | Ch5. Reconnaissance de motif | polys: exemple, parcours arbre |
13 | 25/04/2017 |
Ch5. Reconnaissance de motif
TP: filtres sous Unix |
man 7 re_format
Voir TP de l'an dernier |
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).
La bibliographie que je donne pour le cours de Langages Formels fournit des références supplémentaires pertinentes.
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.