From 086b4847f212f6d120ef59b659ed97c71d8fb897 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Sun, 29 Oct 2017 17:25:25 +0100 Subject: Describe the Thompson automaton of a regular expression. --- notes-inf105.tex | 255 +++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 247 insertions(+), 8 deletions(-) (limited to 'notes-inf105.tex') diff --git a/notes-inf105.tex b/notes-inf105.tex index 3806498..a946e4a 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -2289,10 +2289,11 @@ $q_0$ vers chacun des états initiaux de $A$, puis en éliminant les résultat que ce qui vient d'être dit.) \end{proof} -\thingy On a vu en \ref{dfa-union-and-intersection} une preuve, à base -de NFA, que $L_1 \cup L_2$ est reconnaissable lorsque $L_1$ et $L_2$ -le sont. Donnons maintenant une autre preuve de ce fait, à base de -εNFA : +\medbreak + +On a vu en \ref{dfa-union-and-intersection} une preuve, à base de DFA, +que $L_1 \cup L_2$ est reconnaissable lorsque $L_1$ et $L_2$ le sont. +Donnons maintenant une autre preuve de ce fait, à base de NFA : \begin{prop}\label{nfa-union} Si $L_1,L_2$ sont des langages reconnaissables (sur un même @@ -2579,20 +2580,23 @@ triviaux $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour chaque $x\in\Sigma$). On prendra les suivants : \begin{center} +\begin{tabular}{ll} \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] \node (q0) at (0bp,0bp) [draw,circle,state,initial] {$q_0$}; \end{tikzpicture} -pour le langage $\varnothing$\\ +&pour le langage $\varnothing$ (i.e., pour l'expression rationnelle $\bot$),\\[1.75ex] \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] \node (q0) at (0bp,0bp) [draw,circle,state,initial,final] {$q_0$}; \end{tikzpicture} -pour le langage $\{\varepsilon\}$\\ +&pour le langage $\{\varepsilon\}$ (i.e., pour l'expression +rationnelle $\underline{\varepsilon}$), et\\[1.75ex] \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] \node (q0) at (0bp,0bp) [draw,circle,state,initial] {$q_0$}; \node (q1) at (60bp,0bp) [draw,circle,state,final] {$q_1$}; \draw [->] (q0) to node[auto,swap] {$x$} (q1); \end{tikzpicture} -pour le langage $\{x\}$. +&pour le langage $\{x\}$ (i.e., pour l'expression rationnelle $x$). +\end{tabular} \end{center} \begin{cor}\label{rational-languages-are-recognizable} @@ -2618,7 +2622,7 @@ automate en DFA quitte déterminiser si l'automate accepte le mot. \end{proof} -\thingy Les constructions que nous avons décrites dans cette section +\thingy\label{glushkov-construction} Les constructions que nous avons décrites dans cette section associent naturellement un NFA standard à chaque expression rationnelle : il s'obtient en partant des automates de base décrits en \ref{trivial-standard-automata} et en appliquant les constructions @@ -2760,6 +2764,241 @@ toutes celles aboutissant à l'état $2$ sont étiquetées $b$, et toutes celles aboutissant à $3$ sont étiquetées $c$. +\subsection{L'automate de Thompson (alternative à l'automate de Glushkov)} + +\thingy La construction de Glushkov (exposée +en \ref{glushkov-construction}) d'un automate reconnaissant le langage +dénoté par expression rationnelle $r$ fabrique un NFA. Cette +constrution produit un automate raisonnablement compact (en nombre +d'états), mais il peut être intéressant de disposer d'une autre +construction, plus transparente mais moins efficace : la +\defin[Thompson (construction d'automate de)]{construction de + Thompson} fournit un autre moyen d'associer à une expression +rationnelle $r$ un automate reconnaissant le langage qu'elle dénote. +Elle possède pour sa part les propriétés suivantes : +\begin{itemize} +\item c'est un εNFA reconnaissant le langage $L_r$ dénoté par + l'expression rationnelle $r$ dont on est parti, +\item il possède un unique état initial auquel n'aboutit aucune + transition, et un unique état final duquel ne part aucune + transition, +\item son nombre d'états est égal au double du nombre de symboles + autres que les parenthèses constituant l'expression $r$ (en comptant + aussi bien les lettres de $\Sigma$ que les métacaractères $\bot$, + $\underline{\varepsilon}$, $|$ et $*$ ; mais sans compter la + concaténation implicite). +\end{itemize} + +Dans les dessins qui suivent, on symbolisera de la manière suivante un +automate de Thompson $A$ quelconque : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (30bp,0bp) [draw,dotted,circle,minimum size=50bp] {$A$}; +\node (qi) at (0bp,0bp) [draw,circle,state,initial,fill=white] {$q_0$}; +\node (qf) at (60bp,0bp) [draw,circle,state,final,fill=white] {\vbox to0pt{\vss\hbox to0pt{$q_\infty$\hss}}\phantom{$q_0$}}; +\end{tikzpicture} +\end{center} + +\thingy\label{trivial-thompson-automata} Les automates de Thompson des +langages de base triviaux $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ +(pour chaque $x\in\Sigma$) seront les suivants : + +\begin{center} +\begin{tabular}{ll} +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qi.base)] +\node (qi) at (0bp,0bp) [draw,circle,state,initial] {$q_0$}; +\node (qf) at (60bp,0bp) [draw,circle,state,final] {\vbox to0pt{\vss\hbox to0pt{$q_\infty$\hss}}\phantom{$q_0$}}; +\end{tikzpicture} +&pour le langage $\varnothing$ (i.e., pour l'expression rationnelle $\bot$),\\ +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qi.base)] +\node (qi) at (0bp,0bp) [draw,circle,state,initial] {$q_0$}; +\node (qf) at (60bp,0bp) [draw,circle,state,final] {\vbox to0pt{\vss\hbox to0pt{$q_\infty$\hss}}\phantom{$q_0$}}; +\draw [->] (qi) to node[auto] {$\varepsilon$} (qf); +\end{tikzpicture} +&pour le langage $\{\varepsilon\}$ (i.e., pour l'expression +rationnelle $\underline{\varepsilon}$), et\\ +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qi.base)] +\node (qi) at (0bp,0bp) [draw,circle,state,initial] {$q_0$}; +\node (qf) at (60bp,0bp) [draw,circle,state,final] {\vbox to0pt{\vss\hbox to0pt{$q_\infty$\hss}}\phantom{$q_0$}}; +\draw [->] (qi) to node[auto,swap] {$x$} (qf); +\end{tikzpicture} +&pour le langage $\{x\}$ (i.e., pour l'expression rationnelle $x$). +\end{tabular} +\end{center} + +\thingy\label{thompson-union} Si $A_1$ et $A_2$ sont les automates de +Thompson pour les expressions rationnelles $r_1$ et $r_2$, celui de +$r_1|r_2$ sera construit de la manière suivante : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (30bp,0bp) [draw,dotted,circle,minimum size=50bp] {$A_1$}; +\node (qi) at (0bp,0bp) [draw,circle,state,initial,fill=white] {$q_0$}; +\node (qf) at (60bp,0bp) [draw,circle,state,final,fill=white] {\vbox to0pt{\vss\hbox to0pt{$q_\infty$\hss}}\phantom{$q_0$}}; +\end{tikzpicture} +et +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (30bp,0bp) [draw,dotted,circle,minimum size=50bp] {$A_2$}; +\node (qi) at (0bp,0bp) [draw,circle,state,initial,fill=white] {$q_0$}; +\node (qf) at (60bp,0bp) [draw,circle,state,final,fill=white] {\vbox to0pt{\vss\hbox to0pt{$q_\infty$\hss}}\phantom{$q_0$}}; +\end{tikzpicture} +\\deviennent\\ +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qi.base)] +\node (qi) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q_0$}; +\node (qf) at (95bp,0bp) [draw,circle,state,final,fill=white] {\vbox to0pt{\vss\hbox to0pt{$q_\infty$\hss}}\phantom{$q_0$}}; +\node (A1) at (30bp,35bp) [draw,dotted,circle,minimum size=50bp] {$A_1$}; +\node (qi1) at (0bp,35bp) [draw,circle,state,fill=white] {\phantom{$q_0$}}; +\node (qf1) at (60bp,35bp) [draw,circle,state,fill=white] {\phantom{$q_0$}}; +\node (A2) at (30bp,-35bp) [draw,dotted,circle,minimum size=50bp] {$A_2$}; +\node (qi2) at (0bp,-35bp) [draw,circle,state,fill=white] {\phantom{$q_0$}}; +\node (qf2) at (60bp,-35bp) [draw,circle,state,fill=white] {\phantom{$q_0$}}; +\draw[->] (qi) to node[auto] {$\varepsilon$} (qi1); \draw[->] (qi) to node[auto] {$\varepsilon$} (qi2); +\draw[->] (qf1) to node[auto] {$\varepsilon$} (qf); \draw[->] (qf2) to node[auto] {$\varepsilon$} (qf); +\end{tikzpicture} +\end{center} + +\thingy\label{thompson-concatenation} Si $A_1$ et $A_2$ sont les +automates de Thompson pour les expressions rationnelles $r_1$ et +$r_2$, celui de $r_1 r_2$ sera construit de la manière suivante : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (30bp,0bp) [draw,dotted,circle,minimum size=50bp] {$A_1$}; +\node (qi) at (0bp,0bp) [draw,circle,state,initial,fill=white] {$q_0$}; +\node (qf) at (60bp,0bp) [draw,circle,state,final,fill=white] {\vbox to0pt{\vss\hbox to0pt{$q_\infty$\hss}}\phantom{$q_0$}}; +\end{tikzpicture} +et +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (30bp,0bp) [draw,dotted,circle,minimum size=50bp] {$A_2$}; +\node (qi) at (0bp,0bp) [draw,circle,state,initial,fill=white] {$q_0$}; +\node (qf) at (60bp,0bp) [draw,circle,state,final,fill=white] {\vbox to0pt{\vss\hbox to0pt{$q_\infty$\hss}}\phantom{$q_0$}}; +\end{tikzpicture} +\\deviennent\\ +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qi.base)] +\node (A1) at (30bp,0bp) [draw,dotted,circle,minimum size=50bp] {$A_1$}; +\node (qi) at (0bp,0bp) [draw,circle,state,initial,fill=white] {$q_0$}; +\node (ql) at (60bp,0bp) [draw,circle,state,fill=white] {\phantom{$q_0$}}; +\node (A2) at (150bp,0bp) [draw,dotted,circle,minimum size=50bp] {$A_2$}; +\node (qr) at (120bp,0bp) [draw,circle,state,fill=white] {\phantom{$q_0$}}; +\node (qf) at (180bp,0bp) [draw,circle,state,final,fill=white] {\vbox to0pt{\vss\hbox to0pt{$q_\infty$\hss}}\phantom{$q_0$}}; +\draw[->] (ql) to node[auto] {$\varepsilon$} (qr); +\end{tikzpicture} +\end{center} + +\thingy\label{thompson-star} Si $A$ est l'automate de Thompson pour +l'expression rationnelle $r$, celui de $r{*}$ sera construit de la +manière suivante : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (30bp,0bp) [draw,dotted,circle,minimum size=50bp] {$A$}; +\node (qi) at (0bp,0bp) [draw,circle,state,initial,fill=white] {$q_0$}; +\node (qf) at (60bp,0bp) [draw,circle,state,final,fill=white] {\vbox to0pt{\vss\hbox to0pt{$q_\infty$\hss}}\phantom{$q_0$}}; +\end{tikzpicture} +devient +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (qi) at (0bp,0bp) [draw,circle,state,initial,fill=white] {$q_0$}; +\node (qf) at (180bp,0bp) [draw,circle,state,final,fill=white] {\vbox to0pt{\vss\hbox to0pt{$q_\infty$\hss}}\phantom{$q_0$}}; +\node (A) at (90bp,0bp) [draw,dotted,circle,minimum size=50bp] {$A$}; +\node (qai) at (60bp,0bp) [draw,circle,state,fill=white] {\phantom{$q_0$}}; +\node (qaf) at (120bp,0bp) [draw,circle,state,fill=white] {\phantom{$q_0$}}; +\draw[->] (qi) to node[auto] {$\varepsilon$} (qai); +\draw[->] (qaf) to node[auto] {$\varepsilon$} (qf); +\draw[->] (qi) ..controls (60bp,-60bp) and (120bp,-60bp) .. node[auto] {$\varepsilon$} (qf); +\draw[->] (qaf) ..controls (120bp,60bp) and (60bp,60bp) .. node[auto,above] {$\varepsilon$} (qai); +\end{tikzpicture} +\end{center} + +\thingy Comme on le voit ci-dessus, la construction de Thompson est +très simple à appliquer ; mais elle conduit à des automates rapidement +énormes, comportant un nombre considérable d'états et de transitions +spontanées « stupides ». + +À titre d'exemple, voici l'automate de Thompson, déjà gros, de +l'expression rationnelle $(a|b){*}b$ : + +\begin{center} +\scalebox{0.75}{% +%%% begin example9 %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q1) at (97bp,61bp) [draw,circle,state] {$1$}; + \node (q0) at (18bp,23bp) [draw,circle,state,initial] {$0$}; + \node (q3) at (255bp,138bp) [draw,circle,state] {$3$}; + \node (q2) at (176bp,138bp) [draw,circle,state] {$2$}; + \node (q5) at (255bp,84bp) [draw,circle,state] {$5$}; + \node (q4) at (176bp,84bp) [draw,circle,state] {$4$}; + \node (q7) at (413bp,23bp) [draw,circle,state] {$7$}; + \node (q6) at (334bp,61bp) [draw,circle,state] {$6$}; + \node (q9) at (571bp,23bp) [draw,circle,state,final] {$9$}; + \node (q8) at (492bp,23bp) [draw,circle,state] {$8$}; + \draw [->] (q3) ..controls (280.5bp,113.5bp) and (299.16bp,94.836bp) .. node[auto] {$\varepsilon$} (q6); + \draw [->] (q2) ..controls (203.66bp,138bp) and (215.82bp,138bp) .. node[auto] {$a$} (q3); + \draw [->] (q6) ..controls (303.95bp,58.621bp) and (287.5bp,57.483bp) .. (273bp,57bp) .. controls (221.92bp,55.299bp) and (209.08bp,55.299bp) .. (158bp,57bp) .. controls (147.24bp,57.358bp) and (135.4bp,58.078bp) .. node[auto] {$\varepsilon$} (q1); + \draw [->] (q8) ..controls (519.66bp,23bp) and (531.82bp,23bp) .. node[auto] {$b$} (q9); + \draw [->] (q7) ..controls (440.66bp,23bp) and (452.82bp,23bp) .. node[auto] {$\varepsilon$} (q8); + \draw [->] (q5) ..controls (282.27bp,76.154bp) and (295.19bp,72.293bp) .. node[auto] {$\varepsilon$} (q6); + \draw [->] (q6) ..controls (361.12bp,48.108bp) and (375.27bp,41.127bp) .. node[auto] {$\varepsilon$} (q7); + \draw [->] (q4) ..controls (203.66bp,84bp) and (215.82bp,84bp) .. node[auto] {$b$} (q5); + \draw [->] (q1) ..controls (124.27bp,68.846bp) and (137.19bp,72.707bp) .. node[auto] {$\varepsilon$} (q4); + \draw [->] (q0) ..controls (49.792bp,8.7612bp) and (73.956bp,0bp) .. (96bp,0bp) .. controls (96bp,0bp) and (96bp,0bp) .. (335bp,0bp) .. controls (352.91bp,0bp) and (372.22bp,5.7837bp) .. node[auto] {$\varepsilon$} (q7); + \draw [->] (q0) ..controls (45.123bp,35.892bp) and (59.268bp,42.873bp) .. node[auto] {$\varepsilon$} (q1); + \draw [->] (q1) ..controls (122.5bp,85.495bp) and (141.16bp,104.16bp) .. node[auto] {$\varepsilon$} (q2); +% +\end{tikzpicture} + +%%% end example9 %%% +} +\end{center} + +(Il a $10$ états puisqu'il y a $5$ autres que les parenthèses +dans $(a|b){*}b$.) + +Pour comparaison, voici son automate de Glushkov : + +\begin{center} +%%% begin example9b %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\begin{scope} + \pgfsetstrokecolor{black} + \definecolor{strokecol}{rgb}{1.0,1.0,1.0}; + \pgfsetstrokecolor{strokecol} + \definecolor{fillcol}{rgb}{1.0,1.0,1.0}; + \pgfsetfillcolor{fillcol} +\end{scope} + \node (q9) at (176bp,45.608bp) [draw,circle,state,final] {$9$}; + \node (q0) at (18bp,45.608bp) [draw,circle,state,initial] {$0$}; + \node (q3) at (97bp,150.61bp) [draw,circle,state] {$3$}; + \node (q5) at (97bp,45.608bp) [draw,circle,state] {$5$}; + \draw [->] (q0) ..controls (42.244bp,77.303bp) and (64.303bp,107.38bp) .. node[auto] {$a$} (q3); + \draw [->] (q5) ..controls (124.66bp,45.608bp) and (136.82bp,45.608bp) .. node[auto] {$b$} (q9); + \draw [->] (q3) ..controls (121.24bp,118.91bp) and (143.3bp,88.83bp) .. node[auto] {$b$} (q9); + \draw [->] (q5) to[loop below] node[auto] {$b$} (q5); + \draw [->] (q0) ..controls (45.659bp,45.608bp) and (57.817bp,45.608bp) .. node[auto] {$b$} (q5); + \draw [->] (q0) ..controls (42.871bp,23.135bp) and (60.567bp,9.4181bp) .. (79bp,3.6077bp) .. controls (94.26bp,-1.2026bp) and (99.74bp,-1.2026bp) .. (115bp,3.6077bp) .. controls (129.69bp,8.2379bp) and (143.91bp,17.889bp) .. node[auto] {$b$} (q9); + \draw [->] (q3) to[loop above] node[auto] {$a$} (q3); + \draw [->] (q5) ..controls (112.04bp,72.544bp) and (117.47bp,87.733bp) .. (115bp,101.61bp) .. controls (113.63bp,109.34bp) and (111.12bp,117.45bp) .. node[auto,swap,pos=-0.2] {$a$} (q3); + \draw [->] (q3) ..controls (97bp,116.41bp) and (97bp,92.55bp) .. node[auto,swap,near end] {$b$} (q5); +% +\end{tikzpicture} + +%%% end example9b %%% +\end{center} + +Il a $4$ états puisqu'il y a $3$ lettres dans $(a|b){*}b$. Ces états +ont été étiquetés de manière à illustrer la proposition suivante, qui +fait le lien entre les deux constructions : + +\begin{prop} +L'élimination des transitions spontanées (au sens +de \ref{removal-of-epsilon-transitions}, suivie de la suppression des +états devenus inutiles) dans l'automate de Thompson d'une expression +rationnelle conduit à l'automate de Glushkov de cette même expression. +\end{prop} + + + + \subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA)} \thingy\label{definition-rnfa} Un \defin[automate fini à transitions -- cgit v1.2.3