Clarifications on the state elimination algorithm.

1 files changed, 52 insertions, 19 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index b1d7737..5949a8b 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3070,7 +3070,17 @@ rationnelle conduit à l'automate de Glushkov de cette même expression.
 
 
 
-\subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA)}\label{subsection-rnfa-and-kleenes-algorithm}
+\subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA), algorithme d'élimination des états}\label{subsection-rnfa-and-kleenes-algorithm}
+
+\thingy On cherche dans cette section à montrer la réciproque
+de \ref{rational-languages-are-recognizable}.  On va pour cela donner
+un algorithme (très coûteux !) qui transforme un automate en
+expression rationnelle (dénotant le langage qu'il reconnaît).  Cette
+algorithme « d'élimination des états » fonctionne naturellement sur
+une sorte d'automate encore plus générale que tous ceux que nous avons
+définis jusqu'à présent : on va donc commencer par définir ces
+automates, même si leur intérêt réside presque uniquement en la preuve
+de \ref{recognizable-languages-are-rational} ci-dessous.
 
 \thingy\label{definition-rnfa} Un \defin[automate fini à transitions
   étiquetées par des expressions rationnelles]{automate fini
@@ -3089,8 +3099,8 @@ alphabet $\Sigma$ est la donnée
 \end{itemize}
 Autrement dit, on autorise maintenant des transitions étiquetées par
 des expressions rationnelles quelconques sur $\Sigma$.  Remarquons
-qu'on doit maintenant demander explicitement que l'ensemble $\delta$
-des transitions permises soit fini car l'ensemble $Q \times
+qu'on doit maintenant demander \emph{explicitement} que l'ensemble
+$\delta$ des transitions permises soit fini car l'ensemble $Q \times
 (\mathrm{regexp}(\Sigma)) \times Q$, lui, ne l'est pas.
 
 \thingy\label{rnfa-multiple-transition-relation} Pour un tel automate, on définit une relation $\delta^*
@@ -3127,7 +3137,8 @@ l'expression $r$ elle-même.  Il est évident que ce RNFA reconnaît
 exactement le langage dénoté par $r$.
 
 La représentation graphique des RNFA ne pose pas de problème
-particulier.
+particulier (voir en \ref{example-of-state-elimination} pour
+différents exemples).
 
 \thingy\label{give-rnfa-single-transitions} On peut toujours modifier
 un RNFA de manière à ce qu'il y ait au plus une, ou même si on le
@@ -3152,11 +3163,12 @@ reconnaît le même langage $L_{A'} = L_A$.  De plus, $A'$ se déduit
 algorithmiquement de $A$.
 \end{prop}
 \begin{proof}
-On a vu que pour chaque expression rationnelle $r$ on peut trouver
-(algorithmiquement) un εNFA $A_r$ qui reconnaît le langage dénoté
-par $r$.  On peut donc construire $A'$ en remplaçant chaque transition
-$(q,r,q')$ de $A$ par une copie de l'automate $A_r$ placée entre les
-états $q$ et $q'$.  Symboliquement :
+On a vu en \ref{rational-languages-are-recognizable} que pour chaque
+expression rationnelle $r$ on peut trouver (algorithmiquement) un εNFA
+$A_r$ (par exemple l'automate de Glushkov ou l'automate de Thompson)
+qui reconnaît le langage dénoté par $r$.  On peut donc construire $A'$
+en remplaçant chaque transition $(q,r,q')$ de $A$ par une copie de
+l'automate $A_r$ placée entre les états $q$ et $q'$.  Symboliquement :
 
 \begin{center}
 \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q1.base)]
@@ -3197,11 +3209,11 @@ chemin dans ce dernier, suivi d'une transition spontanée depuis un
 Mais la surprise des RNFA est qu'ils peuvent aussi se ramener à des
 expressions rationnelles !
 
-\begin{prop}
-Soit $A = (Q,I,F,\delta)$ un RNFA sur un alphabet $\Sigma$.  Alors il
-existe une expression rationnelle $r$ sur $\Sigma$ qui dénote le
-langage reconnu par $A$, soit $L_r = L_A$.  De plus, $r$ se déduit
-algorithmiquement de $A$.
+\begin{prop}\label{recognizable-languages-are-rational}
+Soit $A = (Q,I,F,\delta)$ un RNFA (ou, en particulier, un NFA ou
+DFA(I)) sur un alphabet $\Sigma$.  Alors il existe une expression
+rationnelle $r$ sur $\Sigma$ qui dénote le langage reconnu par $A$,
+soit $L_r = L_A$.  De plus, $r$ se déduit algorithmiquement de $A$.
 \end{prop}
 \begin{proof}
 On a vu qu'on pouvait considérer une expression rationnelle comme un
@@ -3275,7 +3287,11 @@ l'expression rationnelle $r$.
 \thingy La procédure qu'on a décrite dans la démonstration de cette
 proposition s'appelle l'algorithme d'\defin{élimination des états} ou
 \index{Kleene (algorithme de)|see{élimination des
-    états}}\textbf{algorithme de Kleene}.
+    états}}\textbf{algorithme de Kleene}\footnote{Peut-être
+  abusivement (le théorème \ref{kleenes-theorem} est indubitablement
+  dû à Kleene, mais le contenu algorithmique ne l'est peut-être pas) ;
+  il est peut-être plus correct d'attribuer l'algorithme à Brzozowski
+  et McCluskey.}.
 
 Il va de soi qu'on peut la simplifier un petit peu : s'il n'y a pas de
 transition de de $q_1$ vers $q$ ou qu'il n'y en a pas de $q$
@@ -3290,7 +3306,9 @@ en passant par $q$.  Et il faut se souvenir que le cas $q_2=q_1$ est à
 traiter aussi.
 
 En général, l'élimination des états conduit à un expression
-extrêmement compliquée.
+extrêmement compliquée (exponentielle dans le nombre d'états de
+l'automate, au moins dans le pire cas, mais aussi dans beaucoup de cas
+« typiques »).
 
 \thingy\label{example-of-state-elimination} À titre d'exemple,
 considérons le DFA suivant sur l'alphabet $\{0,1\}$, qui reconnaît les
@@ -3379,12 +3397,27 @@ conduit à l'automate suivant :
 \noindent et finalement à l'expression rationnelle
 $(0|11|10(1|00){*}01){*}$, qui est équivalente à la précédente.
 
-\begin{cor}
+\bigbreak
+
+Récapitulons le contenu essentiel à retenir comme conséquence
+immédiate de \ref{rational-languages-are-recognizable}
+et \ref{recognizable-languages-are-rational} :
+
+\begin{cor}[Kleene]\label{kleenes-theorem}\index{Kleene (théorème de)}
 La classe des langages rationnels et celle des langages
 reconnaissables coïncident.  (On pourra donc considérer ces termes
 comme synonymes.)
 \end{cor}
 
+Il faut cependant retenir que s'il y a, mathématiquement, équivalence
+entre ces deux classes de langages, cette équivalence \emph{a un coût
+  algorithmique}, c'est-à-dire que la conversion d'une expression
+rationnelle en automate (surtout si on souhaite un DFA), ou à plus
+forte raison d'un automate en expression rationnelle, a une complexité
+exponentielle dans le pire cas.  Il est donc pertinent, en
+informatique, de ne pas considérer les descriptions d'un langage par
+une expression rationnelle, un DFA, et un NFA, comme interchangeables.
+
 
 \subsection{Le lemme de pompage}
 
@@ -3398,7 +3431,7 @@ soit rationnel, si bien qu'on peut arriver à montrer qu'un langage
 n'est pas rationnel en invalidant cette condition (généralement en
 procédant par l'absurde).
 
-\begin{prop}[lemme de pompage pour les langages rationnels]\label{pumping-lemma}
+\begin{prop}[lemme de pompage pour les langages rationnels]\label{pumping-lemma}\index{pompage (lemme de)}
 Soit $L$ un langage rationnel.  Il existe alors un entier $k$ tel que
 tout mot de $t \in L$ de longueur $|t| \geq k$ admette une
 factorisation $t = uvw$ en trois facteurs $u,v,w$ où :
@@ -4774,7 +4807,7 @@ l'intersection des deux, et ce sont ces mots qui forcent ce langage à
 
 \subsection{Le lemme de pompage pour les langages algébriques}
 
-\begin{prop}[lemme de pompage pour les langages algébriques]\label{pumping-lemma-for-algebraic-languages}
+\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$ où :