diff options
| -rw-r--r-- | figs/example7.dot | 24 | ||||
| -rw-r--r-- | figs/example7b.dot | 24 | ||||
| -rw-r--r-- | figs/example7bm.dot | 13 | ||||
| -rw-r--r-- | figs/example7m.dot | 17 | ||||
| -rw-r--r-- | notes-inf105.tex | 137 |
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. + % |