summaryrefslogtreecommitdiffstats log msg author committer range
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
author committer David A. Madore 2016-11-30 16:31:16 +0100 David A. Madore 2016-11-30 16:31:16 +0100 89e92ec19feb388823f66885a633351369c5e809 (patch) 6646b27c874a8275e94c2a8d54803b7ab92d3d58 da6ff34fb72f5dc7d3d1366d53efe81b31a811bc (diff) inf105-89e92ec19feb388823f66885a633351369c5e809.tar.gzinf105-89e92ec19feb388823f66885a633351369c5e809.tar.bz2inf105-89e92ec19feb388823f66885a633351369c5e809.zip
Exercise on determinizing and minimizing an automaton.
-rw-r--r--exercices1.tex208
-rw-r--r--figs/ex1p2a.dot23
-rw-r--r--figs/ex1p2b.dot19
-rw-r--r--figs/ex1p2c.dot36
-rw-r--r--figs/ex1p2d.dot17
5 files changed, 303 insertions, 0 deletions
 diff --git a/exercices1.tex b/exercices1.texindex 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.dotnew file mode 100644index 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.dotnew file mode 100644index 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.dotnew file mode 100644index 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.dotnew file mode 100644index 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"];+}