




L'algorithme exposé ici est appelé \emph{algorithme de Thompson}\index{algorithme!de Thompson}. Il permet de construire un AFND à partir d'une expression rationnelle.

\section{Automates à transitions instantanées}

\begin{Def}[Transition instantanée]
Une \emph{transition instantanée} \index{transition instantanée} est une é\-vo\-lu\-tion possible de l'automate d'un état vers un autre sans qu'aucune entrée ne soit produite.
\end{Def}

Les automates à transitions instantanées interviennent dans l'algorithme de Thompson de construction automatique d'un automate reconnaissant le langage associé à une expression rationnelle...

\section{Données et résultat}
\begin{description}
 \item[Données] une expression rationnelle $r$ sur un alphabet $\Sigma$.
 \item[Résultat] Un AFND $M$ tel que $\mathcal{L}(M) = \mathcal{L}(r)$, qui ne comporte qu'un seul état initial et un seul état d'acceptation...
 \end{description}

\section{Algorithme}

\begin{enumerate}
\item Décomposer l'expression en ses sous-expressions.\\

\item En utilisant les règles (a) et (b) ci-dessous, construire un AFND pour les symboles terminaux de la grammaire ou la chaîne vide (si un même symbole $a$ apparaît plusieurs fois dans l'expression rationnelle, un AFND séparé est construit pour chacune de ses occurences).\\

\item Combiner ensuite récursivement les AFND de base en utilisant la règle (c) jusqu'à obtenir l'AFND pour l'expression rationnelle toute entière.

\begin{enumerate}
 \item Pour $< >$, construire l'AFND :
\begin{center}
 \unitlength = 1mm 
\begin{picture}(57,21)(0,-21)
\put(0,-21){}
\node[NLangle=0.0,Nmarks=i](n12)(16.0,-12.02){d}
\imark(n12)

\node[NLangle=0.0,Nmarks=r](n21)(48.0,-12.01){f}
\rmark(n21)

\drawedge[ELdist=2.5](n12,n21){$\varepsilon$}
\end{picture}
\end{center}

 \item Pour $a \in \Sigma$, construire l'AFND :
\begin{center}
 \unitlength = 1mm 
\begin{picture}(57,21)(0,-21)
\put(0,-21){}
\node[NLangle=0.0,Nmarks=i](n12)(16.0,-12.02){d}
\imark(n12)

\node[NLangle=0.0,Nmarks=r](n21)(48.0,-12.01){f}
\rmark(n21)

\drawedge[ELdist=2.5](n12,n21){a}
\end{picture}
\end{center}
 \item Si $N(s)$ et $N(t)$ sont les AFND pour les expressions rationnelles $s$ et $t$, 
\begin{itemize}
 \item Pour $st$, on construit l'AFND :
\begin{center}
\unitlength = 1mm 
\begin{picture}(115,25)(0,-25)
\put(0,-25){}
\node[NLangle=0.0,Nmarks=i](n12)(16.0,-16.02){d}
\imark(n12)

\node(n13)(60.0,-16.02){}

\node[NLangle=0.0,Nw=64.0,Nh=12.0,Nmr=3.92](n14)(40.0,-16.02){N(s)}

\node[NLangle=0.0,Nmarks=r](n17)(104.0,-16.02){f}

\node[NLangle=0.0,Nw=64.0,Nh=12.0,Nmr=3.92](n16)(80.0,-16.02){N(t)}
\end{picture}
\end{center}

L'état initial de $N(t)$, qui est état d'acceptation pour $N(s)$, perd ce double caractère dans la nouvelle construction.

\item Pour $s|t$, on construit l'AFND
\begin{center}
 \unitlength = 1mm 
\begin{picture}(121,49)(0,-49)
\put(0,-49){}
\node[NLangle=0.0,Nmarks=i](n12)(16.0,-28.01){d}
\imark(n12)

\node(n13)(88.0,-40.01){}

\node[NLangle=0.0,Nw=64.0,Nh=12.0,Nmr=3.92](n14)(64.0,-16.01){N(s)}

\node[NLangle=0.0,Nmarks=r](n17)(112.0,-28.01){f}

\node[NLangle=0.0,Nw=64.0,Nh=12.0,Nmr=3.92](n16)(64.0,-40.01){N(t)}

\node(n20)(40.0,-40.01){}

\node(n21)(40.0,-16.01){}

\node(n22)(88.0,-16.01){}

\drawedge[ELdist=2.5](n12,n21){$\varepsilon$}

\drawedge[ELside=r,ELdist=2.5](n12,n20){$\varepsilon$}

\drawedge[ELside=r,ELdist=2.5](n13,n17){$\varepsilon$}

\drawedge[ELdist=2.5](n22,n17){$\varepsilon$}
\end{picture}
\end{center}

Les états initiaux et les états d'acceptation des AFND de $N(s)$ et de $N(t)$ perdent leur caractère dans le nouvel AFND.

\item Pour l'expression rationnelle $s^*$, on construit l'AFND composé $N(s^*)$ :

\begin{center}
 \unitlength = 1mm 
\begin{picture}(125,57)(0,-57)
\put(0,-57){}
\node[NLangle=0.0,Nmarks=i](n12)(16.0,-28.01){d}
\imark(n12)

\node[NLangle=0.0,Nw=64.0,Nh=12.0,Nmr=3.92](n14)(64.0,-28.01){N(s)}

\node[NLangle=0.0,Nmarks=r](n17)(116.01,-28.01){f}

\node(n21)(40.0,-28.01){}

\node(n22)(88.0,-28.01){}

\drawedge[ELdist=2.5](n12,n21){$\varepsilon$}

\drawedge[ELdist=2.5](n22,n17){$\varepsilon$}

\drawbpedge[ELside=r,ELdist=2.5](n22,89,23.28,n21,87,23.3){$\varepsilon$}

\drawbpedge[ELside=r,ELdist=2.5](n12,-89,24.22,n17,-90,24.7){$\varepsilon$}

\end{picture}
\end{center}


Les états initiaux et les états d'acceptation de $N(s)$ perdent leurs qualités.

\item Pour une expression parenthésée $(s)$, utiliser $N(s)$ lui-même.
\end{itemize}

\end{enumerate}

\end{enumerate}


\section{Exemple}

On applique l'algorithme sur l'exemple : $(a^2|b^2)^*|(a^3|b^3)^*$.

\begin{center}
 \unitlength = 0.85mm 
\begin{picture}(182,119)(0,-119)
\put(0,-119){}
\node[NLangle=0.0,Nmarks=i](n0)(12.0,-52.0){0}

\node[NLangle=0.0](n2)(32.0,-76.0){11}

\node[NLangle=0.0](n3)(56.0,-28.0){2}

\node[NLangle=0.0](n5)(72.0,-16.0){3}

\node[NLangle=0.0](n6)(72.0,-40.0){6}

\node[NLangle=0.0](n7)(92.0,-40.0){7}

\node[NLangle=0.0](n8)(112.0,-40.0){8}

\node[NLangle=0.0](n9)(128.0,-28.0){9}

\node[NLangle=0.0](n10)(92.0,-16.0){4}

\node[NLangle=0.0](n11)(112.0,-16.0){5}

\node[NLangle=0.0](n12)(152.0,-28.0){10}

\node[NLangle=0.0](n13)(52.0,-76.01){12}

\node[NLangle=0.0](n14)(68.0,-64.01){13}

\node[NLangle=0.0](n15)(68.0,-88.01){17}

\node[NLangle=0.0](n16)(84.0,-88.01){18}

\node[NLangle=0.0](n17)(100.0,-88.01){19}

\node[NLangle=0.0](n19)(84.0,-64.01){14}

\node[NLangle=0.0](n20)(100.0,-64.01){15}

\node[NLangle=0.0](n21)(152.0,-76.0){22}

\node[NLangle=0.0,Nmarks=r](n31)(172.0,-52.0){23}

\node[NLangle=0.0](n32)(32.0,-28.0){1}

\drawedge(n32,n3){$\varepsilon$}

\drawedge(n0,n32){$\varepsilon$}

\drawedge(n0,n2){$\varepsilon$}

\drawedge(n2,n13){$\varepsilon$}

\drawedge(n13,n14){$\varepsilon$}

\drawedge(n13,n15){$\varepsilon$}

\drawedge(n14,n19){a}

\drawedge(n15,n16){b}

\drawedge(n19,n20){a}

\drawedge(n16,n17){b}

\drawedge(n21,n31){$\varepsilon$}

\drawedge(n3,n5){$\varepsilon$}

\drawedge(n3,n6){$\varepsilon$}

\drawedge(n6,n7){b}

\drawedge(n7,n8){b}

\drawedge(n8,n9){$\varepsilon$}

\drawedge(n5,n10){a}

\drawedge(n10,n11){a}

\drawedge(n11,n9){$\varepsilon$}

\drawedge(n9,n12){$\varepsilon$}

\drawedge(n12,n31){$\varepsilon$}

\node[NLangle=0.0](n33)(116.0,-64.01){16}

\node[NLangle=0.0](n34)(116.0,-88.01){20}

\node[NLangle=0.0](n35)(132.0,-76.01){21}

\drawedge(n20,n33){a}

\drawedge(n17,n34){b}

\drawedge(n33,n35){$\varepsilon$}

\drawedge(n34,n35){$\varepsilon$}

\drawedge(n35,n21){$\varepsilon$}

\drawbpedge[ELdist=2.0](n35,-269,28.93,n13,89,27.99){$\varepsilon$}

\drawbpedge[ELdist=2.0](n9,-269,32.69,n3,89,32.22){$\varepsilon$}

\drawbpedge[ELside=r,ELdist=2.0](n2,-89,31.99,n21,-89,32.93){$\varepsilon$}

\drawbpedge[ELdist=1.5](n32,-89,28.69,n12,-89,28.22){$\varepsilon$}



\end{picture}
\end{center}



\begin{Exo}
On donne l'expression rationnelle $(a | b)^* | (a^2 | b^2)^*$. 

Utiliser l'algorithme de Thompson pour obtenir un automate non déterministe, à transitions instantanées, reconnaissant le langage.
\end{Exo}


On rappelle que, par définition, sont accessibles sur une entrée donnée $x$ depuis un état donné $e$ : les états accessibles en effectuant successivement 
\begin{itemize}
\item un nombre arbitraire (éventuellement nul) de transitions instantannées,
\item une transition d'entrée $x$ et
\item un nombre arbitraire (éventuellement nul) de transitions instantannées.
\end{itemize}

\begin{Ex}
Pour...
\begin{itemize}
\item L'état 3, avec entrée $a$ : on passe à l'état 4.
\item Si l'entrée $a$ se produit au départ, les états accessibles sont $\{ 4, 14 \}$.
\item Et, à partir de l'état 4 et de l'entrée $a$ : $\{ 5, 9, 2, 10, 23, 3, 6 \}$.\\
\end{itemize}
\end{Ex}

% La variable \og état initial \fg{} d'un automate de Thompson est constituée de l'état initial et de tous les états accessibles depuis celui-ci par un nombre quelconque de transitions instantannée :
% 
% $$\{ 0, 1, 11, 2, 10, 12, 22, 3, 6, 13, 17, 23 \}$$



D'où l'algorithme suivant simplifiant l'automate de l'algorithme de Thompson...

\section{Finalisation}

L'automate construit par algorithme de Thompson n'est pas utilisable tel quel.\\

Il faut en supprimer les transitions instantanées, ce qui se fait par un algorithme voisin de la construction par sous-ensembles. Il faudra, par ailleurs, ensuite, le déterminiser et le minimiser.\\

Soit $M$ l'automate de Thompson obtenu par l'algorithme précédent, $E$ l'ensemble de ses états, $e \in E$ son (unique) état initial et $a \in E$ son (unique) état d'acceptation.\\

On remplace cet automate par un automate $\mathcal{M}$ qui reconnaît le même langage, dont l'ensemble des états est $\mathcal{E}$, l'état initial est $S$, et l'ensemble des états d'acceptation est $A \subset \mathcal{E}$ et qui est obtenu de la manière suivante :

\begin{itemize}
\item $S$ est composé de $e$ et de tous les états de $M$ qui sont accessibles depuis $e$ par un nombre quelconque de transitions instantanées (éventuellement aucune). Dans l'exemple précédent, $$S = \{ 0, 1, 11, 2, 10, 12, 22, 3, 6, 13, 17, 23 \}$$.

\item Soit $Y \in \mathcal{E}$ une partie de l'ensemble des états, et $x$ une entrée. L'image $Y_x$ de $Y$  est constituée des états accessibles depuis un état quelconque de $Y$ par (exactement) une entrée $x$, suivie d'un nombre quelconque de transitions instantanées.

\item $A = \{ Y \in \mathcal{E} | Y \cap \{a\} \neq \emptyset \}$, à savoir les parties $Y$ ci-dessus définies de $E$ qui contiennent l'ancien état d'acceptation.
\end{itemize}


\begin{Exo}
Finalisez l'automate de l'exercice précédent. Le déterminiser, puis obtenir l'automate minimal reconnaissant le même langage.
\end{Exo}


\begin{Exo}[Reprise d'un exercice précédent, version Thompson]
Construire des automates de Moore reconnaissant les langages définis par les expressions rationnelles :
\begin{enumerate}
 \item $(a|b)^* b (a|b)^*$
 \item $((a|b)^2)^* | ((a | b)^3)^*$
 \item $ba^*|ab|(a|bb)ab^*$.
\end{enumerate}
\end{Exo}


\begin{Exo}
 Donner les automates finis minimaux (table de transition, diagrame) reconnaissant les langages associés aux expressions rationnelles suivantes :
\begin{itemize}
 \item $(a|b)^* (aaa|bb)$
 \item $(a|bb)^* abb^*$
\end{itemize}
\end{Exo}

\gsaut
\centerline{\x{Fin du Chapitre}}

