summaryrefslogtreecommitdiffstats
path: root/exercices1.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-30 16:31:16 +0100
committerDavid A. Madore <david+git@madore.org>2016-11-30 16:31:16 +0100
commit89e92ec19feb388823f66885a633351369c5e809 (patch)
tree6646b27c874a8275e94c2a8d54803b7ab92d3d58 /exercices1.tex
parentda6ff34fb72f5dc7d3d1366d53efe81b31a811bc (diff)
downloadinf105-89e92ec19feb388823f66885a633351369c5e809.zip
inf105-89e92ec19feb388823f66885a633351369c5e809.tar.gz
inf105-89e92ec19feb388823f66885a633351369c5e809.tar.bz2
Exercise on determinizing and minimizing an automaton.
Diffstat (limited to 'exercices1.tex')
-rw-r--r--exercices1.tex208
1 files changed, 208 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}