diff options
| -rw-r--r-- | notes-inf105.tex | 115 |
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) : |