summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-inf105.tex115
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) :