summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-10-29 19:21:44 +0100
committerDavid A. Madore <david+git@madore.org>2017-10-29 19:21:44 +0100
commit536f9a4d8db29242e59c84b62f4fb605c0907388 (patch)
treec8186cd6e8540313b2782b82bf23708c70256390
parent4a5151e16ac865e599f86c9872b957314bb720bc (diff)
downloadinf105-536f9a4d8db29242e59c84b62f4fb605c0907388.tar.gz
inf105-536f9a4d8db29242e59c84b62f4fb605c0907388.tar.bz2
inf105-536f9a4d8db29242e59c84b62f4fb605c0907388.zip
Clarifications on the state elimination algorithm.
-rw-r--r--notes-inf105.tex71
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ù :