Reread section on formal grammars. Rewrite proof that algebraic languages are decidable.

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