diff options
Diffstat (limited to 'programme-inf105.tex')
| -rw-r--r-- | programme-inf105.tex | 21 |
1 files changed, 12 insertions, 9 deletions
diff --git a/programme-inf105.tex b/programme-inf105.tex index f6ae6d8..078715b 100644 --- a/programme-inf105.tex +++ b/programme-inf105.tex @@ -74,12 +74,14 @@ reconnaissables. \thingy Stabilité des langages reconnaissables par complémentaire, union, intersection ; stabilité par concaténation et étoile de Kleene. -Les langages rationnels sont reconnaissables. Automate de Thompson. +Les langages rationnels sont reconnaissables. Automate de Thompson +d'une expression rationnelle. Automates à transitions étiquetées par des expressions rationnelles (informellement), équivalence avec les autres sortes d'automates, équivalence avec les expressions rationnelles (par élimination des -états). Équivalence entre langages rationnels et reconnaissables. +états =algorithme de Kleene). Équivalence entre langages rationnels +et reconnaissables. \thingy Énoncé et démonstration du lemme de pompage pour les @@ -91,7 +93,7 @@ DFA minimal\footnote{On conviendra d'utiliser la notion d'automate puits.} (=canonique). Algorithme de minimisation. -\thingy TD sur les automates finis. +\thingy TD sur les automates finis et langages rationnels. \thingy TP sur les expressions régulières et automates finis. @@ -118,14 +120,15 @@ algébrique (admis sans démonstration). (Selon le temps disponible.) L'appartenance d'un mot au langage défini par une grammaire hors contexte est algorithmiquement -décidable\footnote{Par ex., esquisser comment on peut mettre la - grammaire sous forme normale de Chomsky et utiliser l'algorithme de - programmation dynamique (CYK) ?}. Quelques notions sur l'analyse -syntaxique en pratique : notion d'analyseurs descendants et -ascendants. +décidable\footnote{Par ex., en montrant qu'on peut trouver une + grammaire monotone équivalente ; ou bien esquisser comment on peut + mettre la grammaire sous forme normale de Chomsky et utiliser + l'algorithme de programmation dynamique (CYK) ?}. Quelques notions +sur l'analyse syntaxique en pratique : notion d'analyseurs descendants +et ascendants (sans entrer dans les détails). -\thingy TD sur les grammaires hors contexte. +\thingy TD sur les grammaires hors contexte et langages algébriques. \thingy Éléments de calculabilité\footnote{Mieux vaut sans doute ne pas |