Example(s) of minimization algorithm.

5 files changed, 215 insertions, 0 deletions

diff --git a/figs/example7.dot b/figs/example7.dot
new file mode 100644
index 0000000..289a191
--- /dev/null
+++ b/figs/example7.dot
@@ -0,0 +1,24 @@
+digraph example7 {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q0 [style="state,initial",label="0"];
+	q2 [style="state",label="2"];
+	q1 [style="state",label="1"];
+	q4 [style="state,final",label="4"];
+	q3 [style="state",label="3"];
+	q5 [style="state,final",label="5"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q0 [label="b",topath="loop above"];
+	q2 -> q2 [label="a",topath="loop above"];
+	q4 -> q4 [label="a,b",topath="loop above"];
+	q1 -> q1 [label="b",topath="loop below"];
+	q3 -> q3 [label="a,c",topath="loop below"];
+	q5 -> q5 [label="a,b,c",topath="loop below"];
+	q0 -> q1 [label="c"];
+	q0 -> q2 [label="a"];
+	q2 -> q3 [label="c"];
+	q1 -> q3 [label="a,c"];
+	q2 -> q4 [label="b"];
+	q4 -> q5 [label="c"];
+	q3 -> q5 [label="b"];
+}
diff --git a/figs/example7b.dot b/figs/example7b.dot
new file mode 100644
index 0000000..167a79d
--- /dev/null
+++ b/figs/example7b.dot
@@ -0,0 +1,24 @@
+digraph example7b {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q0 [style="state,initial",label="0"];
+	q2 [style="state",label="2"];
+	q1 [style="state",label="1"];
+	q4 [style="state,final",label="4"];
+	q3 [style="state",label="3"];
+	q5 [style="state,final",label="5"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q0 [label="b",topath="loop above"];
+	q2 -> q2 [label="a",topath="loop above"];
+	q4 -> q4 [label="a,b",topath="loop above"];
+	q1 -> q1 [label="b,c",topath="loop below"];
+	q3 -> q3 [label="a,c",topath="loop below"];
+	q5 -> q5 [label="a,b,c",topath="loop below"];
+	q0 -> q1 [label="c"];
+	q0 -> q2 [label="a"];
+	q2 -> q3 [label="c"];
+	q1 -> q3 [label="a"];
+	q2 -> q4 [label="b"];
+	q4 -> q5 [label="c"];
+	q3 -> q5 [label="b"];
+}
diff --git a/figs/example7bm.dot b/figs/example7bm.dot
new file mode 100644
index 0000000..26bfd5e
--- /dev/null
+++ b/figs/example7bm.dot
@@ -0,0 +1,13 @@
+digraph example7bm {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q01 [style="state,initial",label="0|1",texlbl="$0\equiv 1$"];
+	q23 [style="state",label="2|3",texlbl="$2\equiv 3$"];
+	q45 [style="state,final",label="4|5",texlbl="$4\equiv 5$"];
+	edge [texmode="math",lblstyle="auto"];
+	q01 -> q01 [label="b,c",topath="loop above"];
+	q23 -> q23 [label="a,c",topath="loop above"];
+	q45 -> q45 [label="a,b,c",topath="loop above"];
+	q01 -> q23 [label="a"];
+	q23 -> q45 [label="b"];
+}
diff --git a/figs/example7m.dot b/figs/example7m.dot
new file mode 100644
index 0000000..e39cc6a
--- /dev/null
+++ b/figs/example7m.dot
@@ -0,0 +1,17 @@
+digraph example7m {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q0 [style="state,initial",label="0"];
+	q23 [style="state",label="2|3",texlbl="$2\equiv 3$"];
+	q1 [style="state",label="1"];
+	q45 [style="state,final",label="4|5",texlbl="$4\equiv 5$"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q0 [label="b",topath="loop above"];
+	q23 -> q23 [label="a,c",topath="loop above"];
+	q45 -> q45 [label="a,b,c",topath="loop above"];
+	q1 -> q1 [label="b",topath="loop below"];
+	q0 -> q1 [label="c"];
+	q0 -> q23 [label="a"];
+	q1 -> q23 [label="a,c"];
+	q23 -> q45 [label="b"];
+}
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.
+
 
 
 %