From 676afd2ad5c7028a7a8910fb14593897b40c0a11 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 8 Dec 2016 14:57:31 +0100 Subject: Example(s) of minimization algorithm. --- notes-inf105.tex | 137 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 137 insertions(+) (limited to 'notes-inf105.tex') diff --git a/notes-inf105.tex b/notes-inf105.tex index 7c10b3f..7f829fb 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -2590,6 +2590,143 @@ mettre en œuvre de façon plus concrète : du représentant). \end{itemize} +La dernière étape (construction de l'automate) permet de vérifier +qu'on a correctement terminé l'étape précédente (raffinement de la +partition) : si deux états dans la même classe ont une transition +sortante d'étiquette $x$ et qui mènent vers des classes différentes, +c'est que ces états auraient dû être séparés. Il est donc utile de +refaire un contrôle à ce niveau. + +\thingy À titre d'exemple d'exécution de l'algorithme de minimisation, +considérons l'automate suivant : + +\begin{center} +%%% begin example7 %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q1) at (98bp,18bp) [draw,circle,state] {$1$}; + \node (q0) at (18bp,67bp) [draw,circle,state,initial] {$0$}; + \node (q3) at (186bp,18bp) [draw,circle,state] {$3$}; + \node (q2) at (98bp,105bp) [draw,circle,state] {$2$}; + \node (q5) at (266bp,67bp) [draw,circle,state,final] {$5$}; + \node (q4) at (186bp,105bp) [draw,circle,state,final] {$4$}; + \draw [->] (q2) ..controls (125.5bp,78.193bp) and (148.96bp,54.459bp) .. node[auto] {$c$} (q3); + \draw [->] (q0) ..controls (45.307bp,79.816bp) and (60.14bp,87.042bp) .. node[auto] {$a$} (q2); + \draw [->] (q2) to[loop above] node[auto] {$a$} (q2); + \draw [->] (q5) to[loop below] node[auto] {$a,b,c$} (q5); + \draw [->] (q4) ..controls (213.31bp,92.184bp) and (228.14bp,84.958bp) .. node[auto] {$c$} (q5); + \draw [->] (q1) ..controls (128.25bp,18bp) and (144.18bp,18bp) .. node[auto] {$a,c$} (q3); + \draw [->] (q4) to[loop above] node[auto] {$a,b$} (q4); + \draw [->] (q1) to[loop below] node[auto] {$b$} (q1); + \draw [->] (q3) ..controls (213bp,34.334bp) and (228.89bp,44.318bp) .. node[auto] {$b$} (q5); + \draw [->] (q3) to[loop below] node[auto] {$a,c$} (q3); + \draw [->] (q0) ..controls (45.002bp,50.666bp) and (60.894bp,40.682bp) .. node[auto] {$c$} (q1); + \draw [->] (q0) to[loop above] node[auto] {$b$} (q0); + \draw [->] (q2) ..controls (128.25bp,105bp) and (144.18bp,105bp) .. node[auto] {$b$} (q4); +% +\end{tikzpicture} + +%%% end example7 %%% +\end{center} + +Cet automate est bien déterministe, complet et sans état inaccessible. +Dans un premier temps, on partitionne les états en états non-finaux et +finaux, soit $\{0,1,2,3\}$ d'un côté et $\{4,5\}$ de l'autre. +Ensuite, on doit séparer la classe $\{0,1,2,3\}$ en deux selon que la +transition étiquetée par $b$ tombe dans la classe $\{0,1,2,3\}$ +elle-même ou bien dans la classe $\{4,5\}$ : on arrive donc à trois +classes, $\{0,1\}$, $\{2,3\}$ et $\{4,5\}$. Enfin, on doit séparer la +classe $\{0,1\}$ en deux selon que la transition étiquetée par $c$ +tombe dans la classe $\{0,1\}$ elle-même ou bien dans la classe +$\{2,3\}$ : on arrive alors à quatre classes, $\{0\}$, $\{1\}$, +$\{2,3\}$ et $\{4,5\}$, et à l'automate minimal suivant : + +\begin{center} +%%% begin example7m %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q1) at (98bp,18bp) [draw,circle,state] {$1$}; + \node (q0) at (18bp,76bp) [draw,circle,state,initial] {$0$}; + \node (q23) at (190bp,76bp) [draw,circle,state] {$2\equiv 3$}; + \node (q45) at (278bp,76bp) [draw,circle,state,final] {$4\equiv 5$}; + \draw [->] (q1) to[loop below] node[auto] {$b$} (q1); + \draw [->] (q23) to[loop above] node[auto] {$a,c$} (q23); + \draw [->] (q1) ..controls (126.79bp,35.911bp) and (146.9bp,48.867bp) .. node[auto] {$a,c$} (q23); + \draw [->] (q0) ..controls (48.315bp,77.182bp) and (65.168bp,77.757bp) .. (80bp,78bp) .. controls (106.51bp,78.434bp) and (136.64bp,77.795bp) .. node[auto] {$a$} (q23); + \draw [->] (q23) ..controls (222.17bp,76bp) and (234.88bp,76bp) .. node[auto] {$b$} (q45); + \draw [->] (q0) ..controls (44.591bp,56.971bp) and (61.407bp,44.466bp) .. node[auto] {$c$} (q1); + \draw [->] (q0) to[loop above] node[auto] {$b$} (q0); + \draw [->] (q45) to[loop above] node[auto] {$a,b,c$} (q45); +% +\end{tikzpicture} + +%%% end example7m %%% +\end{center} + +Il est intéressant de voir comment des petits changements sur +l'automate initial modifient la minimisation. Si on fait pointer la +transition étiquetée par $c$ de l'état $1$ vers lui-même (au lieu +d'aller vers l'état $3$), c'est-à-dire : + +\begin{center} +%%% begin example7b %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q1) at (98bp,18bp) [draw,circle,state] {$1$}; + \node (q0) at (18bp,67bp) [draw,circle,state,initial] {$0$}; + \node (q3) at (178bp,18bp) [draw,circle,state] {$3$}; + \node (q2) at (98bp,105bp) [draw,circle,state] {$2$}; + \node (q5) at (258bp,67bp) [draw,circle,state,final] {$5$}; + \node (q4) at (178bp,105bp) [draw,circle,state,final] {$4$}; + \draw [->] (q2) ..controls (123.52bp,77.652bp) and (143.78bp,55.049bp) .. node[auto] {$c$} (q3); + \draw [->] (q0) ..controls (45.307bp,79.816bp) and (60.14bp,87.042bp) .. node[auto] {$a$} (q2); + \draw [->] (q2) to[loop above] node[auto] {$a$} (q2); + \draw [->] (q5) to[loop below] node[auto] {$a,b,c$} (q5); + \draw [->] (q4) ..controls (205.31bp,92.184bp) and (220.14bp,84.958bp) .. node[auto] {$c$} (q5); + \draw [->] (q1) ..controls (126.11bp,18bp) and (138.58bp,18bp) .. node[auto] {$a$} (q3); + \draw [->] (q4) to[loop above] node[auto] {$a,b$} (q4); + \draw [->] (q1) to[loop below] node[auto] {$b,c$} (q1); + \draw [->] (q3) ..controls (205bp,34.334bp) and (220.89bp,44.318bp) .. node[auto] {$b$} (q5); + \draw [->] (q3) to[loop below] node[auto] {$a,c$} (q3); + \draw [->] (q0) ..controls (45.002bp,50.666bp) and (60.894bp,40.682bp) .. node[auto] {$c$} (q1); + \draw [->] (q0) to[loop above] node[auto] {$b$} (q0); + \draw [->] (q2) ..controls (126.11bp,105bp) and (138.58bp,105bp) .. node[auto] {$b$} (q4); +% +\end{tikzpicture} + +%%% end example7b %%% +\end{center} + +\noindent alors la minimisation ne sépare pas les états $0$ et $1$, et +on obtient + +\begin{center} +%%% begin example7bm %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q45) at (198bp,21bp) [draw,circle,state,final] {$4\equiv 5$}; + \node (q01) at (22bp,21bp) [draw,circle,state,initial] {$0\equiv 1$}; + \node (q23) at (110bp,21bp) [draw,circle,state] {$2\equiv 3$}; + \draw [->] (q45) to[loop above] node[auto] {$a,b,c$} (q45); + \draw [->] (q23) ..controls (142.17bp,21bp) and (154.88bp,21bp) .. node[auto] {$b$} (q45); + \draw [->] (q23) to[loop above] node[auto] {$a,c$} (q23); + \draw [->] (q01) to[loop above] node[auto] {$b,c$} (q01); + \draw [->] (q01) ..controls (54.17bp,21bp) and (66.885bp,21bp) .. node[auto] {$a$} (q23); +% +\end{tikzpicture} + +%%% end example7bm %%% +\end{center} + +En revanche, si on change l'automate pour rendre l'état $4$ non-final +(avec ou sans la modification précédemment évoquée), la minimisation +aboutit sur la partition triviale en six états, c'est-à-dire que +l'automate est, en fait, déjà minimal. + % -- cgit v1.2.3