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 |
1 | 19/01/2016 | Ch1. Rappels mathématiques | Polycopié: définitions |
2 | 26/01/2016 | Ch1. Rappels mathématiques
Exercices (th. des ensembles, langages formels) |
feuille n°1 |
3 | 02/02/2016 | Ch2. Automates | Voir le polycopié proposé comme synthèse aux étudiants de M1 |
4 | 09/02/2016 | Ch2. Automates | poly: automates à minimiser |
5 | 16/02/2016 | Ch2. Automates (fin)
Ch3. Grammaires formelles |
poly: exemples de grammaires |
6 | 23/02/2016 | séance annulée | |
7 | 01/03/2016 | Ch3. Grammaires formelles | |
8 | 08/03/2016 |
Ch3. Grammaires formelles (fin)
Exercices sur les chapitres 2 & 3 |
feuille n°2
feuille n°3 |
9 | 15/03/2016 | ----- Devoir sur table ----- | |
10 | 22/03/2016 | Ch4. Théorèmes d'équivalence | poly: ER → AFnD |
11 | 29/03/2016 | Ch5. Recherche de motifs | |
12 | 05/04/2016 | TP: à propos de la recherche de motifs et des filtres Unix | poly : man
7 re_format TP : énoncé |
13 | 12/04/2016 | Ch5. Recherche de motifs | polys : exemple ; parcours d'arbre itératif |
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.