diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 182 |
1 files changed, 131 insertions, 51 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 8612eb7..8ee32d7 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -2154,10 +2154,11 @@ et $C(1) = \{1,2\}$ et $C(2) = \{2\}$. Dans tout NFA sans ε-transitions, on a $C(q) = \{q\}$ pour tout état $q$.) Il est clair qu'on peut calculer algorithmiquement $C(q)$ (par exemple -par un algorithme de Dijkstra sur le graphe dont l'ensemble des -sommets est $Q$ et l'ensemble des arêtes est l'ensemble des -ε-transitions de $A$ : la ε-fermeture $C(q)$ est simplement l'ensemble -des sommets accessibles depuis $q$ dans ce graphe). +par un algorithme de Dijkstra / parcours en largeur, sur le graphe +orienté dont l'ensemble des sommets est $Q$ et l'ensemble des arêtes +est l'ensemble des ε-transitions de $A$ : la ε-fermeture $C(q)$ est +simplement l'ensemble des sommets accessibles depuis $q$ dans ce +graphe). \begin{prop}\label{removal-of-epsilon-transitions} Soit $A = (Q,I,F,\delta)$ un εNFA sur un alphabet $\Sigma$. Alors il @@ -2835,29 +2836,42 @@ rationnelle $\underline{\varepsilon}$), et\\[1.75ex] \end{tabular} \end{center} +\bigbreak + +Récapitulons le contenu essentiel de ce que nous avons montré : + \begin{cor}\label{rational-languages-are-recognizable} Tout langage rationnel est reconnaissable ; de plus, un NFA le reconnaissant se déduit algorithmiquement d'une expression rationnelle -le dénotant. (Et en particulier, il est possible de décider -algorithmiquement si un mot vérifie une expression rationnelle.) +le dénotant. + +En particulier, il existe un algorithme qui, donnée une expression +rationnelle $r$ (sur un alphabet $\Sigma$) et un mot $w \in \Sigma^*$, +décide si $w\in L_r$, c'est-à-dire si $w$ vérifie $r$. (Autrement +dit, les langages algébriques sont \emph{décidables} au sens +de \ref{definition-computable-function-or-set}.) \end{cor} \begin{proof} -Cela résulte de façon évidente de la définition des langages -rationnels (cf. §\ref{subsection-rational-languages}), du fait que les -langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour -chaque $x\in\Sigma$) sont reconnaissables par automates finis +L'affirmation du premier paragraphe résulte de façon évidente de la +définition des langages rationnels +(cf. §\ref{subsection-rational-languages}), du fait que les langages +$\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour chaque $x\in\Sigma$) +sont reconnaissables par automates finis (cf. \ref{trivial-standard-automata}), et grâce aux propositions -\ref{nfa-union}, \ref{nfa-concatenation} et \ref{nfa-star}. -(Cf. \ref{glushkov-construction} ci-dessous pour une description -algorithmique plus précise.) - -Pour décider si un mot vérifie une expression rationnelle, on peut -commencer par transformer cette expression rationnelle en NFA standard -(i.e., construire un NFA standard reconnaissant le langage qu'elle -dénote) comme on vient de l'expliquer, et déterminiser ensuite cet -automate (cf. \ref{determinization-of-nfa}), après quoi il est facile -de tester si le DFA résultant de la déterministaion accepte le mot -considéré. +\ref{nfa-union}, \ref{nfa-concatenation} et \ref{nfa-star}. On +renvoie à \ref{glushkov-construction} ci-dessous (ou à +§\ref{subsection-thompson-construction}) pour une description +algorithmique plus précise. + +Pour décider si un mot $w$ vérifie une expression rationnelle $r$, on +commencer par transformer cette expression rationnelle en NFA comme on +vient de l'expliquer (c'est-à-dire à construrie un NFA $A_r$ +reconnaissant le langage $L_r$ dénoté par $r$), puis on déterminise +cet automate (cf. \ref{determinization-of-nfa}), après quoi il est +facile de tester si le DFA résultant de la déterministaion accepte le +mot $w$ considéré (il suffit de suivre l'unique chemin dans l'automate +partant de l'état initial et étiqueté par $w$, et de voir si l'état +auquel il aboutit est final). \end{proof} \thingy\label{glushkov-construction} Les constructions que nous avons @@ -3697,7 +3711,7 @@ doublement exponentielle. %% "Succinctness of the Complement and Intersection of Regular Expressions" -\subsection{Le lemme de pompage} +\subsection{Le lemme de pompage}\label{subsection-pumping-lemma} \thingy On ne dispose à ce stade-là d'aucun moyen pour montrer qu'un langage \emph{n'est pas} rationnel. La @@ -4731,6 +4745,7 @@ 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$. +{\footnotesize On a alors $L(G) = L(G,S)$ où $S$ est l'axiome de $G$, et chaque règle de production $T \rightarrow \alpha_1 | \cdots | \alpha_n$ se traduit par une équation portant sur $L(G,T)$, par exemple $T \rightarrow aUbV @@ -4741,6 +4756,7 @@ d'équations portant sur des langages (par exemple, la grammaire de = (a\,L(G)\,b) \cup \{\varepsilon\}$ : on peut montrer que la définition des grammaires hors contexte revient à considérer la plus petite (au sens de l'inclusion) solution de ce système d'équations. +\par} \bigbreak @@ -5305,14 +5321,22 @@ l'intersection des deux, et ce sont ces mots qui forcent ce langage à \subsection{Le lemme de pompage pour les langages algébriques} +On a vu en §\ref{subsection-pumping-lemma} une condition nécessaire +que doivent vérifier les langages rationnels, et qui est souvent utile +pour montrer qu'un langage \emph{n'est pas} rationnel. Un lemme tout +à fait analogue existe pour les langages algébriques, est qui s'avère +utile dans des circonstance semblables, même si son emploi est plus +difficile ; on prendra garde au fait que, dans l'énoncé suivant, +$x$ et $y$ désignent des mots et non des lettres comme d'habitude : + \begin{prop}[lemme de pompage pour les langages algébriques]\label{pumping-lemma-for-algebraic-languages}\index{pompage (lemme de)} Soit $L$ un langage algébrique. Il existe alors un entier $k$ tel que tout mot de $t \in L$ de longueur $|t| \geq k$ admette une factorisation $t = uvwxy$ en cinq facteurs $u,v,w,x,y \in \Sigma^*$ où : \begin{itemize} -\item[(i)] $|vx| \geq 1$ (c'est-à-dire $v\neq\varepsilon$ \emph{ou - bien} $x\neq\varepsilon$), +\item[(i)] $|vx| \geq 1$ (c'est-à-dire que l'un au moins de $v$ et $x$ + est $\neq\varepsilon$), \item[(ii)] $|vwx| \leq k$, \item[(iii)] pour tout $i\geq 0$ on a $uv^iwx^iy \in L$. \end{itemize} @@ -5435,39 +5459,95 @@ les automates à pile déterministes (qu'il faut définir soigneusement) acceptent strictement moins de langages que les automates à pile non déterministes. -\thingy\label{algebraic-languages-are-decidable} Une approche possible 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 : +\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 : \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 - production soit de longueur $\geq 2$, quitte à traiter spécialement - les éventuels mots de longueur $0$ et $1$ de $L(G)$, + production soit \emph{non vide}, quitte à traiter spécialement la + question de savoir si $\varepsilon \in L(G)$, \item on a ensuite affaire à une grammaire \emph{monotone}, - c'est-à-dire que l'application d'une règle ne peut qu'augmenter la - longueur du pseudo-mot en cours de dérivation, ce qui permet - d'explorer exhaustivement toutes les possibilités et de s'arrêter - dès qu'on dépasse la longueur $|w|$ à atteindre. + c'est-à-dire que l'application d'une règle ne peut qu'augmenter (au + sens large) la longueur du pseudo-mot en cours de dérivation, ce qui + permet d'explorer exhaustivement toutes les possibilités et de + s'arrêter dès qu'on dépasse la longueur $|w|$ à atteindre. \end{itemize} -Pour ce qui est de la première partie : l'idée est d'éliminer d'abord -les règles $T \rightarrow U$ (où $U$ est un nonterminal) : ces règles -peuvent s'éliminer quitte à ajouter une règle $T \rightarrow \alpha$ -pour toute règle $U \rightarrow \alpha$ : on procède comme pour -l'élimination des ε-transitions dans les εNFA (autrement dit, si on a -une règle $V \rightarrow \alpha$ avec $V$ un nonterminal qui peut être -dérivé par une suite de règles $T \rightarrow \cdots \rightarrow V$ en -partant de $V$, on crée une règle $T \rightarrow \alpha$). Ensuite, -si on dispose de règles $T \rightarrow \varepsilon$ ou $T \rightarrow -x$ (où $x$ est une lettre), on peut supprimer ces règles quitte à -ajouter à chaque règle ayant un $T$ dans le membre de droite la même -règle où $T$ a été remplacé par $\varepsilon$ ou $U$ ou $x$ selon le -cas ; il faudra simplement faire un cas spécial, si $T$ est l'axiome -de la grammaire, pour retenir que le mot $\varepsilon$ ou $x$ peut -être produit. À titre d'exemple, dans la grammaire $S \rightarrow -aSbS \,|\, \varepsilon$, on peut écarter la règle $S \rightarrow -\varepsilon$ quitte à ajouter des règles $S \rightarrow aSb$ et $S -\rightarrow abS$ et $S \rightarrow ab$. +Énonçons précisément le résultat en question : + +\begin{thm}\label{algebraic-languages-are-decidable} +Il existe un algorithme qui, donnée une grammaire hors-contexte $G$ +(sur un alphabet $\Sigma$) et un mot $w \in \Sigma^*$, décide si $w +\in L(G)$. Autrement dit, les langages algébriques sont +\emph{décidables} au sens +de \ref{definition-computable-function-or-set}. + +Plus exactement, on montre : +\begin{itemize} +\item Il existe un algorithme qui, donnée une grammaire + hors-contexte $G$ (sur un alphabet $\Sigma$), calcule une grammaire + $G'$ (sur le même alphabet $\Sigma$ et ayant le même ensemble $N$ de + nonterminaux que $G$) dont toutes les productions sont soit de la + forme $T \rightarrow \alpha$ avec $|\alpha| \geq 1$, et une partie + $E$ de $\{\varepsilon\}$ (c'est-à-dire soit $\varnothing$ soit + $\{\varepsilon\}$), telles que $L(G) = L(G') \cup E$. +\item Il existe un algorithme qui, donnée une grammaire $G'$ comme on + vient de le dire, et un mot $w \in \Sigma^*$, décide si $w \in + L(G')$. +\end{itemize} +\end{thm} +\begin{proof} +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 » +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 +l'ensemble des nonterminaux évanescents de la manière suivante : on +commence avec $N_0 = \varnothing$, et tant qu'il existe dans $G$ une +règle $T \rightarrow \alpha$, pour laquelle $T$ n'est pas encore +dans $N_0$, avec $\alpha \in N_0^*$ (c'est-à-dire, ne faisant +intervenir que des nonterminaux connus pour être évanescents ; y +compris $\alpha = \varepsilon$), on ajoute $T$ à $N_0$ et on +recommence. Cette boucle va évidemment terminer en temps fini (il n'y +a qu'un nombre fini de nonterminaux) et lorsque c'est le cas $N_0$ +sera l'ensemble des nonterminaux évanescents. + +Une fois calculé l'ensemble $N_0$ des nonterminaux évanescents, on +peut définir $G'$ de la manière suivante : pour chaque production $T +\rightarrow \alpha$ de $G$, on met dans $G'$ toutes les productions $T +\rightarrow \alpha'$ où $\alpha'$ est un sous-(pseudo-)mot +$\neq\varepsilon$ de $\alpha$ obtenu en effaçant un sous-ensemble +quelconque de ses nonterminaux évanescents. La grammaire $G'$ est +alors « presque » faiblement équivalente à $G$ : tout arbre de +dérivation dans $G'$ donne un arbre de dérivation du même mot +dans $G$, quitte à ajouter, à chaque fois qu'une règle $T \rightarrow +\alpha'$ est utilisée dans $G'$, les nonterminaux évanescents +manquants, qui portent eux-mêmes un sous-arbre de dérivation du mot +vide (puisqu'ils sont, justement, évanescents) ; et réciproquement, +tout arbre de dérivation dans $G$ en donne un dans $G'$ quitte à +effacer tout sous-arbre qui ne porte que des feuilles $\varepsilon$ +(ce qui assure que sa racine est évanescente). La seule subtilité est +qu'on a éventuellement perdu le mot vide dans $L(G)$ (la procédure +qu'on vient de décrire conduisant à effacer la totalité de l'arbre), +mais il suffit de poser $E = \{\varepsilon\}$ exactement lorsque +l'axiome $S$ de $G$ est évanescent pour corriger ce problème. + +Montrons maintenant l'affirmation du second point. Pour cela, on +considère l'ensemble (fini !) $(\Sigma\cup N)^{\leq|w|}$ de tous les +pseudo-mots de longueur $\leq |w|$. On construit et on explore +progressivement (par exemple par un algorithme de Dijkstra / parcours +en largeur), à partir de $S$, le graphe sur cet ensemble de sommets +dont les arêtes sont les dérivations immédiates de $G'$ à condition +que le membre de droite soit de longueur $\leq |w|$ : comme la +grammaire $G'$ est monotone, toute dérivation de $w$ sera un chemin +dans le graphe qu'on vient de dire (elle ne peut pas passer par des +pseudo-mots de longueur $>|w|$), donc on peut détecter sur ce graphe +fini si une telle dérivation existe. +\end{proof} \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 |