Regexp-labeled automata, equivalence with NFAs and with regexps.

1 files changed, 216 insertions, 0 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 05844ca..11a081c 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1818,6 +1818,222 @@ et \ref{nfa-star}.
   y mène).}
 
 
+\subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA)}
+
+\thingy Un \textbf{automate fini (non-déterministe) à transitions
+  étiquetées par des expressions rationnelles}, en abrégé
+\textbf{RNFA}, sur un alphabet $\Sigma$ est la donnée
+\begin{itemize}
+\item d'un ensemble fini $Q$ d'états,
+\item d'un ensemble $I \subseteq Q$ d'états dits initiaux,
+\item d'un ensemble $F \subseteq Q$ d'états dits finaux,
+\item d'un ensemble \emph{fini} de transitions $\delta \subseteq Q
+  \times (\mathrm{regexp}(\Sigma)) \times Q$ où
+  $(\mathrm{regexp}(\Sigma))$ désigne l'ensemble des expressions
+  rationnelles sur $\Sigma$.
+\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
+(\mathrm{regexp}(\Sigma)) \times Q$, lui, ne l'est pas.
+
+\thingy Pour un tel automate, on définit une relation $\delta^*
+\subseteq Q \times \Sigma^* \times Q$ par $(q,w,q') \in \delta^*$
+lorsqu'il existe $q_0,\ldots,q_n \in Q$ et $r_1,\ldots,r_n \in
+\mathrm{regexp}(\Sigma)$ tels que $q_0 = q$ et $q_n = q'$ et
+$(q_{i-1},r_i,q_i) \in\delta$ pour chaque $1\leq i\leq n$, et enfin $w
+\in L_{r_1\cdots r_n}$.
+
+Concrètement, $(q,w,q') \in \delta^{(n)}$ signifie que le RNFA peut
+passer de l'état $q$ à l'état $q'$ en effectuant des transitions
+($q_0\to q_1 \to \cdots \to q_n$ étiquetées par $r_1,\ldots,r_n \in
+\mathrm{regexp}(\Sigma)$) et en consommant le mot $w$ au sens où ce
+dernier se décompose comme concaténation d'autant de facteurs que de
+transitions ($w = v_1\cdots v_n$), chacun vérifiant l'expression
+rationnelle qui étiquette la transition (soit $v_i \in L_{r_i}$).
+
+Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$
+et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$.  Le
+langage accepté $L_A$ et l'équivalence de deux automates sont définis
+de façon analogue aux DFA
+(cf. \ref{definition-recognizable-language}).
+
+\thingy Un εNFA (ou \textit{a fortiori} un NFA, DFAI ou DFA) est
+considéré comme un RNFA particulier dont les transitions sont
+étiquetées soit par une unique lettre (considérée comme expression
+rationnelle) soit par le symbole $\underline{\varepsilon}$ (dénotant
+le langage $\{\varepsilon\}$) dans le cas des transitions spontanées.
+
+Une expression rationnelle $r$ peut aussi être considérée comme un
+RNFA particulier comportant un unique état initial, un unique état
+final, et une unique transition de l'un vers l'autre, étiquetée par
+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.
+
+\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
+souhaite, exactement une, transition entre deux états $q$ et $q'$
+donnés.  En effet, s'il existe plusieurs transitions
+$(q,r_1,q'),\ldots, \penalty0 (q,r_k,q') \in \delta$ possibles entre
+$q$ et $q'$, on peut les remplacer par une unique transition
+$(q,(r_1|\cdots|r_k),q')$, cela ne change visiblement rien au
+fonctionnement de l'automate (et notamment pas le langage reconnu).
+S'il n'y a \emph{aucune} transition de $q$ vers $q'$, on peut toujours
+choisir d'en ajouter une $(q,\bot,q')$ (qui ne peut pas être
+empruntée !) si c'est commode.
+
+Comme les εNFA, les NFA et les DFAI avant eux, les RNFA peuvent se
+ramener aux automates précédemment définis :
+
+\begin{prop}
+Soit $A = (Q,I,F,\delta)$ un RNFA sur un alphabet $\Sigma$.  Alors il
+existe un εNFA $A' = (Q',I',F',\delta')$ (sur le même
+alphabet $\Sigma$) et qui soit équivalent à $A$ au sens où il
+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 :
+
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q1.base)]
+\node (q1) at (0bp,0bp) [draw,circle,state] {$q$};
+\node (q2) at (70bp,0bp) [draw,circle,state] {$q'$};
+  \draw [->] (q1) to node[auto] {$r$} (q2);
+\end{tikzpicture}
+\quad devient\quad
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q1.base)]
+\node (q1) at (0bp,0bp) [draw,circle,state] {$q$};
+\node (q2) at (100bp,0bp) [draw,circle,state] {$q'$};
+\node (A) at (50bp,0bp) [draw,dotted,circle] {$A_r$};
+  \draw [->] (q1) to node[auto] {$\varepsilon$} (A);
+  \draw [->] (A) to node[auto] {$\varepsilon$} (q2);
+\end{tikzpicture}
+\end{center}
+
+Plus précisément, si $\{(q_j,r_j,q'_j) : 1\leq j\leq M\}$ est une
+énumération de $\delta$, on construit $A'$ en lui donnant pour
+ensemble d'états $Q \uplus \biguplus_{j=1}^M Q_{r_j}$ où $Q_{r_j}$ est
+l'ensemble d'états de l'automate $A_{r_j}$ construit pour
+reconnaître $r_j$, les ensembles d'états initiaux et finaux sont
+$I'=I$ et $F'=F$ comme dans $A$, et la relation de transition
+$\delta'$ est la réunion de chacune $\delta_{r_j}$ de celle des
+εNFA $A_{r_j}$ à quoi on ajoute encore des transitions spontanées
+$(q_j,\varepsilon,q^\sharp)$ pour tout état initial $q^\sharp \in
+I_{r_j}$ de $A_{r_j}$ et des transitions spontanées
+$(q^\flat,\varepsilon,q'_j)$ pour tout état final $q^\flat \in
+F_{r_j}$ de $A_{r_j}$.  Il est clair que faire un chemin dans $A'$
+revient à un faire un chemin dans $A$ où, à chaque fois qu'on fait la
+transition $q_j\to q'_j$ étiquetée par $r_j$, on la remplace par un
+chemin $q_j \to q^\sharp \to \cdots \to q^\flat \to q'_j$ formé d'une
+transition spontanée vers un état initial de $A_{r_j}$ suivi d'un
+chemin dans ce dernier, suivi d'une transition spontanée depuis un
+état final de $A_{r_j}$.
+\end{proof}
+
+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$.
+\end{prop}
+\begin{proof}
+On a vu qu'on pouvait considérer une expression rationnelle comme un
+RNFA ayant un unique état initial, un unique état final, et une unique
+transition de l'un vers l'autre (étiquetée par l'expression
+rationnelle en question).  On va construire montrer que $A$ est
+équivalent à un RNFA de cette nature, ce qui montrera bien qu'il est
+équivalent à une expression rationnelle.
+
+Remarquons tout d'abord qu'on peut supposer que $A$ a un unique état
+initial $q_0$ sans aucune transition qui y aboutit (si ce n'est pas le
+cas, il suffit de créer un nouvel état $q_0$, d'en faire le seul état
+initial, et de le munir de transitions spontanées — c'est-à-dire
+étiquetées par $\underline{\varepsilon}$ — vers tous les états
+précédemment initiaux).  De même (symétriquement), on peut supposer
+que $A$ a un unique état final $q_\infty$ sans aucune transition qui
+en part.  On fera l'hypothèse que $A$ a ces propriétés, et on
+s'arrangera pour les préserver dans ce qui suit.
+
+Soient maintenant $q$ un état de $A$ qui n'est ni l'état initial ni
+l'état final.  On va montrer qu'on peut \emph{éliminer} $q$,
+c'est-à-dire, quitte à ajouter des transitions, remplacer $A$ par un
+automate équivalent $A'$ qui n'a pas cet état.  Pour cela, soient
+$q_1,q_2$ deux états quelconques de $A$, autres que $q$ mais
+possiblement égaux entre eux, où $q_1$ peut être l'état initial (mais
+pas l'état final) et $q_2$ peut être l'état final (mais pas l'état
+initial).  On a vu en \ref{give-rnfa-single-transitions} qu'on pouvait
+supposer qu'il existait une unique transition $(q_1,r_{12},q_2)$ et de
+même $(q_1,r_1,q)$ et $(q,r_2,q_2)$ et $(q,s,q)$ (transition de $q$
+vers lui-même).  En même temps qu'on supprime $q$, on met dans $A'$ la
+transition $(r_{12}|r_1(s){*}r_2)$ entre $q_1$ et $q_2$.
+Symboliquement :
+
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q1.base)]
+\node (q1) at (0bp,0bp) [draw,circle,state] {$q_1$};
+\node (q2) at (70bp,0bp) [draw,circle,state] {$q_2$};
+\node (q) at (35bp,50bp) [draw,circle,state] {$q$};
+  \draw [->] (q1) to node[auto] {$r_{12}$} (q2);
+  \draw [->] (q1) to node[auto] {$r_1$} (q);
+  \draw [->] (q) to node[auto] {$r_2$} (q2);
+  \draw [->] (q) to[loop above] node[auto] {$s$} (q);
+\end{tikzpicture}
+\quad devient\quad
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q1.base)]
+\node (q1) at (0bp,0bp) [draw,circle,state] {$q_1$};
+\node (q2) at (100bp,0bp) [draw,circle,state] {$q_2$};
+  \draw [->] (q1) to node[auto] {$\scriptstyle (r_{12}|r_1(s){*}r_2)$} (q2);
+\end{tikzpicture}
+\end{center}
+
+Cette transformation doit être effectuée \emph{simultanément pour
+  toute paire} $(q_1,q_2)$ d'états de $A$ pour laquelle
+$q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$ : pour chaque
+telle paire, on remplace l'étiquette de la transition $r_{12}$ entre
+eux par $(r_{12}|r_1(s){*}r_2)$.  Ceci ne change pas le fonctionnement
+de l'automate, car tout chemin dans $A$ peut être remplacé par un
+chemin dans $A'$ en supprimant simplement les $q$ (si on considère
+$q_1$ et $q_2$ les états avant un bloc de de $q$ dans le chemin, on
+voit que le chemin $q_1 \to q \to q \to \cdots \to q \to q_2$ peut se
+transformer en $q_1 \to q_2$ en consommant un mot qui vérifie
+l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$).
+
+En supprimant (dans n'importe quel ordre) tous les états autres que
+$q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant une unique
+transition $(q_0,r,q_\infty)$, qui est donc essentiellement
+l'expression rationnelle $r$.
+\end{proof}
+
+\thingy La procédure qu'on a décrite dans la démonstration de cette
+proposition s'appelle l'algorithme d'\textbf{élimination des états}.
+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$
+vers $q_2$ (c'est-à-dire que soit $r_1$ soit $r_2$ doit être considéré
+comme valant $\bot$), on ne touche simplement pas à $r_{12}$ (et si la
+transition de $q_1$ vers $q_2$ n'existait pas non plus, il n'y a pas
+besoin de la créer) ; de même, s'il n'y a pas de transition de $q$
+vers lui-même, on ignore la partie $s{*}$.  En revanche, il faut bien
+penser à créer une transition de $q_1$ vers $q_2$, même si elle
+n'existait pas au départ, lorsqu'on peut arriver de l'un vers l'autre
+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.
+
+
 %
 %
 %