summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-12-08 13:57:31 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-12-08 13:57:31 (GMT)
commit676afd2ad5c7028a7a8910fb14593897b40c0a11 (patch)
treee9e2cc4ef1d9141a14eb06e73df753aed06a0516
parentba099a706121527209c6f02076c48c808977fd60 (diff)
downloadinf105-676afd2ad5c7028a7a8910fb14593897b40c0a11.zip
inf105-676afd2ad5c7028a7a8910fb14593897b40c0a11.tar.gz
inf105-676afd2ad5c7028a7a8910fb14593897b40c0a11.tar.bz2
Example(s) of minimization algorithm.
-rw-r--r--figs/example7.dot24
-rw-r--r--figs/example7b.dot24
-rw-r--r--figs/example7bm.dot13
-rw-r--r--figs/example7m.dot17
-rw-r--r--notes-inf105.tex137
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.
+
%