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