diff options
| -rw-r--r-- | programme-inf105.tex | 15 |
1 files changed, 9 insertions, 6 deletions
diff --git a/programme-inf105.tex b/programme-inf105.tex index 59b34c0..450ece8 100644 --- a/programme-inf105.tex +++ b/programme-inf105.tex @@ -115,14 +115,17 @@ grammaire à un DFA ou NFA. (Selon le temps disponible.) L'appartenance d'un mot au langage défini par une grammaire hors contexte est algorithmiquement -décidable. Quelques idées sur l'analyse syntaxique en pratique : -notion d'analyseurs descendants et ascendants. +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. \thingy TD sur les grammaires hors contexte. -\thingy Notions de calculabilité\footnote{Mieux vaut sans doute ne pas +\thingy Éléments de calculabilité\footnote{Mieux vaut sans doute ne pas perdre de temps à introduire un modèle de calculabilité particulier (machine de Turing ou fonctions générales récursives, par exemple) : insister sur le fait que tout langage de programmation raisonnable, @@ -131,9 +134,9 @@ d'un algorithme, thèse de Church-Turing. Ensembles/langages\footnote{Souligner qu'ici contrairement au reste du cours, on peut indifféremment considérer des ensembles d'entiers - naturels ou de mots.} décidables (=récursifs) et semi-décidables -(=récursivement énumérables). Notion de machine universelle. -Indécidabilité du problème de l'arrêt. + naturels ou de mots.} décidables (=calculables, =récursifs) et +semi-décidables (=semi-calculables, =récursivement énumérables). +Notion de machine universelle. Indécidabilité du problème de l'arrêt. \thingy TP sur les grammaires hors contexte avec JavaCC. |