A brief description of the CYK dynamic programming algorithm for CFGs.

1 files changed, 107 insertions, 8 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 60877a5..e08083d 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -4739,11 +4739,13 @@ VV'|\varepsilon$).  Nous éviterons ces extensions aux grammaires hors
 contexte pour ne pas introduire de confusion.
 \par}
 
-\thingy Il peut être utile, pour raisonner sur les langages
-algébriques, d'introduire, lorsque $G$ est une grammaire hors contexte
-et $T$ un nonterminal quelconque, le langage $L(G,T)$ des mots qui
-dérivent de $T$, c'est-à-dire le langage engendré par la grammaire
-$G'$ identique à $G$ à ceci près que son axiome est $T$.
+\thingy\label{words-deriving-from-another-nonterminal} Il peut être
+utile, pour raisonner sur les langages algébriques, d'introduire,
+lorsque $G$ est une grammaire hors contexte et $T$ un nonterminal
+quelconque, le langage $L(G,T) := \{w \in \Sigma^* : T
+\mathrel{\Rightarrow^*_G} w\}$ des mots qui dérivent de $T$,
+c'est-à-dire le langage engendré par la grammaire $G'$ identique à $G$
+à ceci près que son axiome est $T$.
 
 {\footnotesize
 On a alors $L(G) = L(G,S)$ où $S$ est l'axiome de $G$, et chaque règle
@@ -5386,7 +5388,7 @@ en \ref{example-of-pumping-lemma-for-algebraic-languages} qu'il n'est
 pas algébrique ; c'est donc que $L$ n'est pas non plus algébrique.
 
 
-\subsection{Notions sur l'analyse des langages hors contexte}
+\subsection{Notions sur l'analyse algorithmique des langages hors contexte}
 
 \thingy Il est naturel de se poser la question suivante : existe-t-il
 un algorithme qui, donnée une grammaire hors contexte $G$, permet de
@@ -5461,8 +5463,8 @@ non déterministes.
 
 \thingy Une approche simple, quoique terriblement inefficace, pour
 résoudre algorithmiquement, \emph{en théorie}, le problème de décider
-si un mot $w$ appartient au langage $L(G)$ engendré par une
-grammaire $G$ est la suivante :
+si un mot $w$ appartient au langage $L(G)$ engendré par une grammaire
+hors contexte $G$ (absolument quelconque) est la suivante :
 \begin{itemize}
 \item réécrire la grammaire (i.e., la remplacer par une grammaire
   équivalente) de manière à ce que le membre de droite de chaque
@@ -5549,6 +5551,103 @@ pseudo-mots de longueur $>|w|$), donc on peut détecter sur ce graphe
 fini si une telle dérivation existe.
 \end{proof}
 
+{\footnotesize
+
+\thingy\label{handwaving-on-dynamical-programming} Expliquons comment
+on peut approcher de façon algorithmiquement plus efficace le problème
+de reconnaître si $w \in L(G)$, et fournir une autre démonstration du
+théorème \ref{algebraic-languages-are-decidable}, tout en continuant à
+ne faire aucune hypothèse sur la grammaire hors contexte $G$.
+
+Il s'agit de travailler en deux étapes :
+\begin{itemize}
+\item D'abord, trouver algorithmiquement une grammaire $G'$ et un $E
+  \subseteq \{\varepsilon\}$ tels que $L(G) = L(G') \cup E$, et que
+  $G'$ soit en \defin[Chomsky (forme normale de)]{forme normale de
+    Chomsky}, c'est-à-dire que toute production de $G'$ est de la
+  forme $T \rightarrow UV$ avec $U,V$ (exactement) deux nonterminaux,
+  ou bien $T \rightarrow x$ avec $x$ un terminal.
+\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$.
+\end{itemize}
+
+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
+  \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.
+\item Pour chaque règle $T \rightarrow U_1 \cdots U_n$ dont le membre
+  de droite est de longueur $n\geq 3$, introduire $n-2$ nouveaux
+  nonterminaux $Z_1,\ldots, Z_{n-2}$ et remplacer la règle $T
+  \rightarrow U_1 \cdots U_n$ par les $n-1$ règles $T \rightarrow U_1
+  Z_1$ et $Z_i \rightarrow U_{i+1} Z_{i+1}$ pour $1\leq i\leq n-3$ et
+  $Z_{n-2} \rightarrow U_{n-1} U_n$.  Ceci permet de faire en sorte
+  que le membre de droite de chaque règle soit de longueur $\leq 2$.
+\item Éliminer les règles produisant $\varepsilon$ (et calculer
+  l'ensemble $E$) exactement comme dans la démonstration du premier
+  point de \ref{algebraic-languages-are-decidable}.  À ce stade-là, le
+  membre de droite de chaque règle est de longueur exactement
+  $1$ ou $2$ (et dans le second cas, constitué de deux nonterminaux).
+\item Pour chaque règle $U \rightarrow \alpha$ où $\alpha$ n'est pas
+  un unique nonterminal, et chaque terminal tel qu'il existe une suite
+  $T \rightarrow \cdots \rightarrow V$ de règles produisant à chaque
+  fois un unique nonterminal, et réécrivant $T$ en $V$, introduire une
+  règle $T \rightarrow \alpha$, puis supprimer toutes les règles dont
+  le membre de droite est un unique nonterminal.  (Cette
+  transformation fonctionne exactement comme l'élimination des
+  ε-transitions d'un εNFA, cf. \ref{removal-of-epsilon-transitions},
+  si on imagine que les règles de la forme $T \rightarrow U$ sont des
+  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.
+
+Une fois la grammaire $G'$ en forme normale de Chomsky connue,
+lorsqu'on a un mot $w$ dont on cherche à tester s'il appartient
+à $L(G')$, on calcule, pour chaque facteur $u$ de $w$ (identifié par
+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\}$) :
+\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
+  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
+  récurrence), et chaque $Y$ tel que la règle $Y \rightarrow X_1 X_2$
+  soit dans $G'$, mettre l'élément $Y$ dans $\Lambda(u)$.
+\end{itemize}
+
+Il n'est pas difficile de se convaincre que ceci construit bien les
+ensembles $\Lambda(u)$ annoncés : la deuxième partie revient à
+rechercher toutes les dérivations $Y \Rightarrow X_1 X_2
+\mathrel{\Rightarrow^*} v_1 v_2 = u$ possibles dans lesquelles $X_1$ a
+donné $v_1$ et $X_2$ a donné $v_2$.  Une fois les $\Lambda(u)$ connus,
+tester si $w \in L(G')$ revient à tester si $S \in \Lambda(w)$.
+
+L'algorithme qu'on vient de décrire (pour tester si $w \in L(G')$ une
+fois $G'$ sous forme normale de Chomsky) porte le nom
+d'\defin[Cocke-Younger-Kasami (algorithme de)]{algorithme de
+  Cocke–Younger–Kasami} ou algorithme \index{CYK (algorithme
+  de)|see{Cocke-Younger-Kasami}}\textbf{CYK}.  Sa complexitée est
+cubique en la longueur de $w$.
+
+\par}
+
 \thingy\label{handwaving-on-ll-and-lr} Du point de vue pratique, il existe deux approches principales
 pour analyser les langages définis par des grammaires hors contexte
 (supposées \emph{au minimum} inambiguës) :