Exercise on determinizing and minimizing an automaton.

5 files changed, 303 insertions, 0 deletions

diff --git a/exercices1.tex b/exercices1.tex
index 1eb8b74..f3a7115 100644
--- a/exercices1.tex
+++ b/exercices1.tex
@@ -239,4 +239,212 @@ s'agit d'un multiple non-trivial ($n+1\geq 2$) de $p$.
 %
 %
 %
+
+\exercice
+
+On considère l'automate suivant :
+\begin{center}
+%%% begin ex1p2a %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (98bp,72bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,47bp) [draw,circle,state,initial] {$0$};
+  \node (q3) at (258bp,72bp) [draw,circle,state] {$3$};
+  \node (q2) at (178bp,72bp) [draw,circle,state] {$2$};
+  \node (q5) at (178bp,18bp) [draw,circle,state] {$5$};
+  \node (q4) at (98bp,18bp) [draw,circle,state] {$4$};
+  \node (q7) at (338bp,47bp) [draw,circle,state,final] {$7$};
+  \node (q6) at (258bp,18bp) [draw,circle,state] {$6$};
+  \draw [->] (q2) ..controls (206.11bp,72bp) and (218.58bp,72bp)  .. node[auto] {$a$} (q3);
+  \draw [->] (q3) ..controls (285.85bp,63.395bp) and (299.33bp,59.074bp)  .. node[auto] {$\varepsilon$} (q7);
+  \draw [->] (q7) to[loop below] node[auto] {$a,b$} (q7);
+  \draw [->] (q6) ..controls (285.62bp,27.897bp) and (299.46bp,33.043bp)  .. node[auto] {$\varepsilon$} (q7);
+  \draw [->] (q4) ..controls (126.11bp,18bp) and (138.58bp,18bp)  .. node[auto] {$b$} (q5);
+  \draw [->] (q0) to[loop below] node[auto] {$a,b$} (q0);
+  \draw [->] (q0) ..controls (45.62bp,37.103bp) and (59.462bp,31.957bp)  .. node[auto] {$\varepsilon$} (q4);
+  \draw [->] (q5) ..controls (206.11bp,18bp) and (218.58bp,18bp)  .. node[auto] {$b$} (q6);
+  \draw [->] (q0) ..controls (45.849bp,55.605bp) and (59.331bp,59.926bp)  .. node[auto] {$\varepsilon$} (q1);
+  \draw [->] (q1) ..controls (126.11bp,72bp) and (138.58bp,72bp)  .. node[auto] {$a$} (q2);
+%
+\end{tikzpicture}
+
+%%% end ex1p2a %%%
+\end{center}
+
+(0) Décrire brièvement le langage accepté par l'automate en question.
+
+(1) Cet automate est-il déterministe ?  Si non, le déterminiser.
+
+(2) Minimiser l'automate déterminisé (on doit trouver un DFA ayant
+quatre états).  Décrire brièvement la signification de ces quatre
+états, de façon à vérifier qu'il accepte le même langage que décrit
+en (0).
+
+\begin{corrige}
+(0) L'automate proposé accepte les mots ayant soit deux $a$
+  consécutifs (en passant par le chemin $0\to 1\to 2\to 3\to 7$) soit
+  deux $b$ consécutifs (en passant par le chemin $0\to 4\to 5\to 6\to
+  7$).
+
+(1) L'automate ayant des ε-transitions, il ne peut pas être
+  déterministe : on a affaire à un εNFA.  Avant de le déterminiser, on
+  élimine ses ε-transitions : la ε-fermeture de $0$ est $\{1,4\}$,
+  celle de $3$ est $\{3,7\}$ et celle de $6$ est $\{6,7\}$ ; on est
+  amené au NFA suivant :
+\begin{center}
+%%% begin ex1p2b %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q0) at (18bp,47bp) [draw,circle,state,initial] {$0$};
+  \node (q3) at (178bp,72bp) [draw,circle,state,final,accepting above] {$3$};
+  \node (q2) at (98bp,72bp) [draw,circle,state] {$2$};
+  \node (q5) at (98bp,18bp) [draw,circle,state] {$5$};
+  \node (q7) at (268bp,47bp) [draw,circle,state,final] {$7$};
+  \node (q6) at (178bp,18bp) [draw,circle,state,final,accepting below] {$6$};
+  \draw [->] (q2) ..controls (126.11bp,72bp) and (138.58bp,72bp)  .. node[auto] {$a$} (q3);
+  \draw [->] (q3) ..controls (208.21bp,63.701bp) and (225.92bp,58.67bp)  .. node[auto] {$a,b$} (q7);
+  \draw [->] (q7) to[loop below] node[auto] {$a,b$} (q7);
+  \draw [->] (q6) ..controls (208.34bp,27.667bp) and (226.26bp,33.576bp)  .. node[auto] {$a,b$} (q7);
+  \draw [->] (q5) ..controls (126.11bp,18bp) and (138.58bp,18bp)  .. node[auto] {$b$} (q6);
+  \draw [->] (q0) ..controls (45.62bp,37.103bp) and (59.462bp,31.957bp)  .. node[auto] {$b$} (q5);
+  \draw [->] (q0) ..controls (45.849bp,55.605bp) and (59.331bp,59.926bp)  .. node[auto] {$a$} (q2);
+  \draw [->] (q0) to[loop below] node[auto] {$a,b$} (q0);
+%
+\end{tikzpicture}
+
+%%% end ex1p2b %%%
+\end{center}
+(Les états $1$ et $4$ étant inaccessibles, ils ont été retirés.)
+
+On peut maintenant procéder à la minimisation.  Pour abréger les noms
+des états, on note, par exemple, $023$ pour $\{0,2,3\}$.  En
+construisant de proche en proche, on obtient le DFA suivant :
+\begin{center}
+\scalebox{0.8}{%PLEASE!  There HAS to be a better way to do this!
+%%% begin ex1p2c %%%
+
+\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}
+\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}
+\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}
+\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 (q0) at (18bp,120.98bp) [draw,circle,state,initial] {$0$};
+  \node (q027) at (382bp,28.975bp) [draw,circle,state,final] {$027$};
+  \node (q056) at (188bp,57.975bp) [draw,circle,state,final,accepting below] {$056$};
+  \node (q023) at (188bp,165.98bp) [draw,circle,state,final,accepting above] {$023$};
+  \node (q057) at (382bp,203.98bp) [draw,circle,state,final] {$057$};
+  \node (q0567) at (285bp,57.975bp) [draw,circle,state,final,accepting above] {$0567$};
+  \node (q02) at (100bp,159.98bp) [draw,circle,state] {$02$};
+  \node (q0237) at (285bp,165.98bp) [draw,circle,state,final,accepting below] {$0237$};
+  \node (q05) at (100bp,67.975bp) [draw,circle,state] {$05$};
+  \draw [->] (q057) ..controls (359.08bp,178.5bp) and (349.99bp,170.92bp)  .. (340bp,166.98bp) .. controls (334.88bp,164.95bp) and (329.26bp,163.8bp)  .. node[auto] {$a$} (q0237);
+  \draw [->] (q027) ..controls (382bp,83.608bp) and (382bp,135.55bp)  .. node[auto] {$b$} (q057);
+  \draw [->] (q0) ..controls (45.352bp,133.82bp) and (60.273bp,141.1bp)  .. node[auto] {$a$} (q02);
+  \draw [->] (q0237) to[loop above] node[auto] {$a$} (q0237);
+  \draw [->] (q023) ..controls (213.27bp,203.14bp) and (232.48bp,225.93bp)  .. (256bp,235.98bp) .. controls (287.74bp,249.53bp) and (326.56bp,235.18bp)  .. node[auto] {$b$} (q057);
+  \draw [->] (q023) ..controls (222.58bp,165.98bp) and (234.64bp,165.98bp)  .. node[auto] {$a$} (q0237);
+  \draw [->] (q02) ..controls (129.57bp,161.97bp) and (142.05bp,162.84bp)  .. node[auto] {$a$} (q023);
+  \draw [->] (q0567) to[loop below] node[auto] {$b$} (q0567);
+  \draw [->] (q05) ..controls (129.65bp,64.644bp) and (142.24bp,63.18bp)  .. node[auto] {$b$} (q056);
+  \draw [->] (q027) ..controls (353.26bp,40.441bp) and (346.42bp,42.961bp)  .. (340bp,44.975bp) .. controls (334.59bp,46.672bp) and (328.83bp,48.274bp)  .. node[auto,above] {$b$} (q0567);
+  \draw [->] (q056) ..controls (222.58bp,57.975bp) and (234.64bp,57.975bp)  .. node[auto] {$b$} (q0567);
+  \draw [->] (q0237) ..controls (323.66bp,181.04bp) and (337.58bp,186.61bp)  .. node[auto] {$b$} (q057);
+  \draw [->] (q056) ..controls (217.15bp,27.882bp) and (235.83bp,11.989bp)  .. (256bp,4.9751bp) .. controls (287.46bp,-5.9647bp) and (325.21bp,4.3005bp)  .. node[auto] {$a$} (q027);
+  \draw [->] (q05) ..controls (100bp,99.927bp) and (100bp,116.29bp)  .. node[auto] {$a$} (q02);
+  \draw [->] (q057) ..controls (396.19bp,163.02bp) and (402.5bp,136.5bp)  .. (400bp,112.95bp) .. controls (398.21bp,96.085bp) and (394.46bp,77.628bp)  .. node[auto] {$a$} (q027);
+  \draw [->] (q0567) ..controls (315.48bp,36.675bp) and (323.74bp,32.382bp)  .. (332bp,29.975bp) .. controls (336.98bp,28.524bp) and (342.36bp,27.708bp)  .. node[auto,below] {$a$} (q027);
+  \draw [->] (q02) ..controls (115.85bp,134.18bp) and (120.35bp,121.75bp)  .. (118bp,110.23bp) .. controls (116.93bp,104.99bp) and (115.19bp,99.598bp)  .. node[auto] {$b$} (q05);
+  \draw [->] (q0) ..controls (45.218bp,103.61bp) and (61.545bp,92.789bp)  .. node[auto] {$b$} (q05);
+%
+\end{tikzpicture}
+
+%%% end ex1p2c %%%
+}
+\end{center}
+(À titre d'exemple, la transition étiquetée $b$ partant de l'état
+$023$ conduit à l'état $057$ car les transitions étiquetées $b$ dans
+le NFA précédent et partant des états parmi $\{0,2,3\}$ sont $0\to 0$,
+$0\to 5$, $3\to 7$ et $7\to 7$.  Tous les états contenant l'un des
+symboles $3,6,7$ sont finaux.)
+
+(2) On a affaire à un DFA dont tous les états sont accessibles, on
+peut donc appliquer directement l'algorithme de Moore.  Une première
+partition sépare les états finaux, soit $023, 0237, 027, 056, 0567,
+057$ des non-finaux, soit $0, 02, 05$.  L'étape suivante distingue
+$02$ parce que sa $a$-transition conduit à une classe différente que
+celles de $0$ et $05$, et $05$ parce que sa $b$-transition conduit à
+une classe différente de $0$ et $02$.  Finalement, on arrive à un
+automate à quatre états :
+\begin{center}
+%%% begin ex1p2d %%%
+
+\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}
+  \filldraw (0bp,0bp) -- (0bp,112bp) -- (200bp,112bp) -- (200bp,0bp) -- cycle;
+\end{scope}
+  \node (q02) at (100bp,93bp) [draw,circle,state] {$02$};
+  \node (q0) at (18bp,56bp) [draw,circle,state,initial] {$0$};
+  \node (qA) at (182bp,60bp) [draw,circle,state,final] {$A$};
+  \node (q05) at (100bp,19bp) [draw,circle,state] {$05$};
+  \draw [->] (q0) ..controls (45.691bp,68.345bp) and (60.407bp,75.151bp)  .. node[auto] {$a$} (q02);
+  \draw [->] (qA) to[loop below] node[auto] {$a,b$} (qA);
+  \draw [->] (q02) ..controls (129.2bp,81.367bp) and (143.35bp,75.529bp)  .. node[auto] {$a$} (qA);
+  \draw [->] (q05) ..controls (128.81bp,33.252bp) and (143.85bp,40.959bp)  .. node[auto,below] {$b$} (qA);
+  \draw [->] (q05) ..controls (100bp,46.09bp) and (100bp,55.041bp)  .. node[auto] {$a$} (q02);
+  \draw [->] (q02) ..controls (116.71bp,70.13bp) and (120.2bp,60.948bp)  .. (118bp,52.251bp) .. controls (117.33bp,49.598bp) and (116.4bp,46.928bp)  .. node[auto] {$b$} (q05);
+  \draw [->] (q0) ..controls (45.691bp,43.655bp) and (60.407bp,36.849bp)  .. node[auto] {$b$} (q05);
+%
+\end{tikzpicture}
+
+%%% end ex1p2d %%%
+\end{center}
+où $A$ représente la classe de tous les états finaux de l'automate
+précédent.
+
+La signification des quatre états est la suivante : l'état $0$
+signifie que l'automate n'a encore rien lu, l'état $02$ signifie que
+l'automate vient de lire un $a$, le $05$ signifie qu'il vient de lire
+un $b$, le $A$ signifie qu'il a lu deux $a$ consécutifs ou bien deux
+$b$ consécutifs.  Sur cette description, il est clair que l'automate
+accepte les mots contenant deux $a$ consécutifs ou bien deux $b$
+consécutifs.
+\end{corrige}
+
+
+%
+%
+%
 \end{document}
diff --git a/figs/ex1p2a.dot b/figs/ex1p2a.dot
new file mode 100644
index 0000000..41870a1
--- /dev/null
+++ b/figs/ex1p2a.dot
@@ -0,0 +1,23 @@
+digraph ex1p2a {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q0 [style="state,initial",label="0"];
+	q1 [style="state",label="1"];
+	q2 [style="state",label="2"];
+	q3 [style="state",label="3"];
+	q4 [style="state",label="4"];
+	q5 [style="state",label="5"];
+	q6 [style="state",label="6"];
+	q7 [style="state,final",label="7"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q0 [label="a,b",topath="loop below"];
+	q0 -> q1 [label="e",texlbl="$\varepsilon$"];
+	q0 -> q4 [label="e",texlbl="$\varepsilon$"];
+	q1 -> q2 [label="a"];
+	q4 -> q5 [label="b"];
+	q2 -> q3 [label="a"];
+	q5 -> q6 [label="b"];
+	q3 -> q7 [label="e",texlbl="$\varepsilon$"];
+	q6 -> q7 [label="e",texlbl="$\varepsilon$"];
+	q7 -> q7 [label="a,b",topath="loop below"];
+}
diff --git a/figs/ex1p2b.dot b/figs/ex1p2b.dot
new file mode 100644
index 0000000..34ed531
--- /dev/null
+++ b/figs/ex1p2b.dot
@@ -0,0 +1,19 @@
+digraph ex1p2b {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q0 [style="state,initial",label="0"];
+	q2 [style="state",label="2"];
+	q3 [style="state,final,accepting above",label="3"];
+	q5 [style="state",label="5"];
+	q6 [style="state,final,accepting below",label="6"];
+	q7 [style="state,final",label="7"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q0 [label="a,b",topath="loop below"];
+	q0 -> q2 [label="a"];
+	q0 -> q5 [label="b"];
+	q2 -> q3 [label="a"];
+	q5 -> q6 [label="b"];
+	q3 -> q7 [label="a,b"];
+	q6 -> q7 [label="a,b"];
+	q7 -> q7 [label="a,b",topath="loop below"];
+}
diff --git a/figs/ex1p2c.dot b/figs/ex1p2c.dot
new file mode 100644
index 0000000..84317c1
--- /dev/null
+++ b/figs/ex1p2c.dot
@@ -0,0 +1,36 @@
+digraph ex1p2c {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q0 [style="state,initial",label="0"];
+	q05 [style="state",label="05"];
+	q056 [style="state,final,accepting below",label="056"];
+	q02 [style="state",label="02"];
+	q023 [style="state,final,accepting above",label="023"];
+	q057 [style="state,final",label="057"];
+	q0567 [style="state,final,accepting above",label="0567"];
+	q027 [style="state,final",label="027"];
+	q0237 [style="state,final,accepting below",label="0237"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q05 [label="b"];
+	q0 -> q02 [label="a"];
+	q05 -> q02 [label="a"];
+	q02 -> q05 [label="b"];
+	{ rank="same"; q05; q02; }
+	q05 -> q056 [label="b"];
+	q02 -> q023 [label="a"];
+	q056 -> q0567 [label="b"];
+	q056 -> q027 [label="a"];
+	q023 -> q0237 [label="a"];
+	q023 -> q057 [label="b"];
+	{ rank="same"; q056; q023; }
+	q0567 -> q027 [label="a",lblstyle="auto,below"];
+	q027 -> q057 [label="b"];
+	q057 -> q0237 [label="a"];
+	q0237 -> q057 [label="b"];
+	q057 -> q027 [label="a"];
+	q027 -> q0567 [label="b",lblstyle="auto,above"];
+	{ rank="same"; q057; q027; }
+	{ rank="same"; q0567; q0237; }
+	q0237 -> q0237 [label="a",topath="loop above"];
+	q0567 -> q0567 [label="b",topath="loop below"];
+}
diff --git a/figs/ex1p2d.dot b/figs/ex1p2d.dot
new file mode 100644
index 0000000..7dd540c
--- /dev/null
+++ b/figs/ex1p2d.dot
@@ -0,0 +1,17 @@
+digraph ex1p2d {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q0 [style="state,initial",label="0"];
+	q05 [style="state",label="05"];
+	q02 [style="state",label="02"];
+	qA [style="state,final",label="A"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q05 [label="b"];
+	q0 -> q02 [label="a"];
+	q05 -> q02 [label="a"];
+	q02 -> q05 [label="b"];
+	{ rank="same"; q05; q02; }
+	q05 -> qA [label="b",lblstyle="auto,below"];
+	q02 -> qA [label="a"];
+	qA -> qA [label="a,b",topath="loop below"];
+}