Reread description of CYK algorithm.

1 files changed, 15 insertions, 14 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index e08083d..470a46c 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -5504,7 +5504,7 @@ Plus exactement, on montre :
 Montrons d'abord l'affirmation du premier point.
 
 Pour cela, on va d'abord calculer l'ensemble $N_0$ des nonterminaux
-« évanescents » de $G$, un nonterminal $T$ étant dit « évanescent »
+« \index{évanescent (nonterminal)}évanescents » de $G$, un nonterminal $T$ étant dit « évanescent »
 lorsque $T \mathrel{\Rightarrow^*} \varepsilon$.  Mais il est évident
 que toute dérivation de $\varepsilon$ dans $G$ ne peut faire
 intervenir que des nonterminaux évanescents.  On peut donc calculer
@@ -5570,7 +5570,8 @@ Il s'agit de travailler en deux étapes :
 \item Ensuite, utiliser un algorithme de programmation dynamique pour
   calculer, pour chaque facteur $u$ de $w$ (par ordre croissant de
   taille), l'ensemble de tous les terminaux $T$ tels que $T
-  \mathrel{\Rightarrow^*} u$.
+  \mathrel{\Rightarrow^*} u$ (ce qui répond notamment à la question de
+  savoir si $S \mathrel{\Rightarrow^*} w$).
 \end{itemize}
 
 Détaillons un peu plus chacune de ces étapes.
@@ -5578,9 +5579,9 @@ Détaillons un peu plus chacune de ces étapes.
 Pour transformer la grammaire $G$ en une grammaire $G'$ sous forme
 normale de Chomsky, on effectue les transformations suivantes :
 \begin{itemize}
-\item Introduire pour chaque terminal $x$ un nonterminal $X$ et une
-  règle $X \rightarrow x$, et remplacer chaque occurrence de $x$
-  par $X$ dans le membre de droite de toute règle autre que $X
+\item Introduire pour chaque terminal $x$ un nouveau nonterminal $X$
+  et une règle $X \rightarrow x$, et remplacer chaque occurrence
+  de $x$ par $X$ dans le membre de droite de toute règle autre que $X
   \rightarrow x$.  Ceci permet de faire en sorte qu'à part les règles
   $X \rightarrow x$, le membre de droite de toute règle soit
   uniquement constitué de nonterminaux.
@@ -5608,8 +5609,8 @@ normale de Chomsky, on effectue les transformations suivantes :
   sortes de transitions spontanées d'un nonterminal vers un autre.)
 \end{itemize}
 
-L'ordre de ces transformations peut être légèrement varié, mais
-l'ordre proposé ci-dessus est sans doute le meilleur.
+L'ordre de ces transformations peut être légèrement varié, mais celui
+proposé ci-dessus est sans doute le meilleur.
 
 Une fois la grammaire $G'$ en forme normale de Chomsky connue,
 lorsqu'on a un mot $w$ dont on cherche à tester s'il appartient
@@ -5618,13 +5619,13 @@ son point de départ et sa longueur), dans l'ordre croissant de
 longueur, l'ensemble $\Lambda(u)$ des nonterminaux $T$ tels que $u \in
 L(G',T)$ (on rappelle,
 cf. \ref{words-deriving-from-another-nonterminal}, que $L(G',T) :=
-\{w \in \Sigma^* : T \mathrel{\Rightarrow^*} w\}$) :
+\{v \in \Sigma^* : T \mathrel{\Rightarrow^*} v\}$) :
 \begin{itemize}
 \item Si $|u|=1$, c'est-à-dire $u \in \Sigma$, il s'agit simplement de
   l'ensemble des $T$ tels que la règle $T \rightarrow u$ soit
   dans $G'$.
 \item Si $|u|\geq 2$, considérer chaque factorisation $u = v_1 v_2$ en
-  facteurs de taille $\geq 1$ (il y en a $|u|-1$ possibles), pour
+  deux facteurs de taille $\geq 1$ (il y en a $|u|-1$ possibles), pour
   chacune d'entre elles, pour chaque $X_1 \in \Lambda(v_1)$ (i.e., tel
   que $v_1 \in L(G',X_1)$) et chaque $X_2 \in \Lambda(v_2)$ (i.e., tel
   que $v_2 \in L(G',X_2)$) (ces deux ensembles étant connus par
@@ -5658,7 +5659,7 @@ pour analyser les langages définis par des grammaires hors contexte
   en partant de la racine et en descendant jusqu'aux
   feuilles\footnote{En botanique, un arbre a la racine en bas et les
     feuilles en haut ; en informatique, on les représente plutôt
-    racine en haut et feuille en bas.}.
+    racine en haut et feuilles en bas.}.
 \item Les analyseurs \defin[LR (analyse)]{LR} procèdent de façon \emph{ascendante} (en
   anglais « bottom-up »), parcourent le mot depuis la gauche (« L »)
   et génèrent la dérivation droite (« R ») de l'arbre d'analyse
@@ -5689,8 +5690,8 @@ lettre $a$, ce qui permet de distinguer les mots dérivant des règles
 $S\rightarrow TS$ et $S\rightarrow c$, on va écrire :
 \begin{itemize}
 \item Fonction « rechercher un préfixe qui dérive de $S$ » (prenant en
-  entrée un mot $w\in\{a,b\}^*$ et renvoyant un préfixe de $w$ et un
-  arbre de dérivation de $w$ à partir de $S$ :
+  entrée un mot $w\in\{a,b\}^*$, et renvoyant un préfixe de $w$ et un
+  arbre de dérivation de $w$ à partir de $S$) :
 \begin{itemize}
 \item si la première lettre de $w$ est $c$, renvoyer le préfixe $c$ et
   l'arbre trivial $S\to c$, sinon :
@@ -5709,8 +5710,8 @@ $S\rightarrow TS$ et $S\rightarrow c$, on va écrire :
   respectivement).
 \end{itemize}
 \item Fonction « rechercher un préfixe qui dérive de $T$ » (prenant en
-  entrée un mot $u\in\{a,b\}^*$ et renvoyant un préfixe de $u$ et un
-  arbre de dérivation de $u$ à partir de $T$ :
+  entrée un mot $u\in\{a,b\}^*$, et renvoyant un préfixe de $u$ et un
+  arbre de dérivation de $u$ à partir de $T$) :
 \begin{itemize}
 \item vérifier que la première lettre est un $a$ (sinon, soulever une
   exception indiquant une erreur d'analyse),