An exercise on finite automata.

4 files changed, 251 insertions, 0 deletions

diff --git a/exercices3.tex b/exercices3.tex
index 2d3d5a5..bc0b77f 100644
--- a/exercices3.tex
+++ b/exercices3.tex
@@ -92,6 +92,187 @@ Git: \input{vcline.tex}
 %
 %
 
+\bigbreak
+\centerline{\textbf{Langages rationnels et automates}}
+
+\exercice
+
+Soit $\Sigma = \{a,b\}$.
+
+(1) Tracer l'automate de Thompson de l'expression rationnelle
+$a{*}(baa{*}){*}$.  Cet automate est-il déterministe ?
+
+(2) En éliminer les transitions spontanées.
+
+(3) Déterminiser l'automate obtenu.
+
+(4) Minimiser l'automate obtenu.
+
+(5) Vérifier le résultat en décrivant en français le langage dénoté
+par l'expression rationnelle initiale et reconnu par l'automate
+finalement obtenu.
+
+\begin{corrige}
+(1) L'automate de Thompson de $a{*}(baa{*}){*}$ doit comporter $14$
+  états puisque cette expression rationnelle contient $7$ symboles
+  parenthèses non comptées.  Il est le suivant (où on a omis les
+  $\varepsilon$ sur les transitions spontanées) :
+\begin{center}
+\scalebox{0.34}{%
+%%% begin ex3p1 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (97bp,45bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
+  \node (q3) at (255bp,18bp) [draw,circle,state] {$3$};
+  \node (q2) at (176bp,45bp) [draw,circle,state] {$2$};
+  \node (q5) at (413bp,48bp) [draw,circle,state] {$5$};
+  \node (q4) at (334bp,18bp) [draw,circle,state] {$4$};
+  \node (q7) at (571bp,86bp) [draw,circle,state] {$7$};
+  \node (q6) at (492bp,86bp) [draw,circle,state] {$6$};
+  \node (q9) at (729bp,86bp) [draw,circle,state] {$9$};
+  \node (q8) at (650bp,86bp) [draw,circle,state] {$8$};
+  \node (q11) at (891.49bp,125bp) [draw,circle,state] {$11$};
+  \node (q10) at (809.5bp,125bp) [draw,circle,state] {$10$};
+  \node (q13) at (1055.5bp,25bp) [draw,circle,state,final] {$13$};
+  \node (q12) at (973.49bp,63bp) [draw,circle,state] {$12$};
+  \draw [->] (q0) ..controls (59.7bp,17.371bp) and (103.03bp,16.838bp)  .. (140bp,17bp) .. controls (169.56bp,17.13bp) and (203.43bp,17.448bp)  .. node[auto] {{}} (q3);
+  \draw [->] (q12) ..controls (939.5bp,48.432bp) and (914.89bp,40bp)  .. (892.49bp,40bp) .. controls (491bp,40bp) and (491bp,40bp)  .. (491bp,40bp) .. controls (474.34bp,40bp) and (455.77bp,41.875bp)  .. node[auto] {{}} (q5);
+  \draw [->] (q2) ..controls (203.44bp,35.73bp) and (216.64bp,31.102bp)  .. node[auto] {{}} (q3);
+  \draw [->] (q10) ..controls (835.62bp,135.26bp) and (845.21bp,137.3bp)  .. (854bp,136bp) .. controls (856.94bp,135.57bp) and (859.98bp,134.94bp)  .. node[auto] {$a$} (q11);
+  \draw [->] (q7) ..controls (598.66bp,86bp) and (610.82bp,86bp)  .. node[auto] {$a$} (q8);
+  \draw [->] (q9) ..controls (788.12bp,80.488bp) and (892.85bp,70.553bp)  .. node[auto] {{}} (q12);
+  \draw [->] (q8) ..controls (677.66bp,86bp) and (689.82bp,86bp)  .. node[auto] {{}} (q9);
+  \draw [->] (q11) ..controls (915.87bp,107.43bp) and (926.56bp,99.325bp)  .. (935.99bp,92bp) .. controls (940.47bp,88.526bp) and (945.22bp,84.783bp)  .. node[auto] {{}} (q12);
+  \draw [->] (q2) ..controls (152.62bp,39.018bp) and (146.07bp,37.685bp)  .. (140bp,37bp) .. controls (134.92bp,36.427bp) and (129.53bp,36.741bp)  .. node[auto] {{}} (q1);
+  \draw [->] (q6) ..controls (519.66bp,86bp) and (531.82bp,86bp)  .. node[auto] {{}} (q7);
+  \draw [->] (q12) ..controls (1002.2bp,49.853bp) and (1016.2bp,43.176bp)  .. node[auto] {{}} (q13);
+  \draw [->] (q9) ..controls (756.02bp,98.925bp) and (770.16bp,105.95bp)  .. node[auto] {{}} (q10);
+  \draw [->] (q3) ..controls (282.66bp,18bp) and (294.82bp,18bp)  .. node[auto] {{}} (q4);
+  \draw [->] (q11) ..controls (866.59bp,118.91bp) and (860.06bp,117.66bp)  .. (854bp,117bp) .. controls (848.92bp,116.45bp) and (843.55bp,116.73bp)  .. node[auto] {{}} (q10);
+  \draw [->] (q5) ..controls (440.12bp,60.892bp) and (454.27bp,67.873bp)  .. node[auto] {$b$} (q6);
+  \draw [->] (q4) ..controls (366.77bp,7.9414bp) and (390.7bp,2bp)  .. (412bp,2bp) .. controls (412bp,2bp) and (412bp,2bp)  .. (974.49bp,2bp) .. controls (992.87bp,2bp) and (1012.7bp,7.6737bp)  .. node[auto] {{}} (q13);
+  \draw [->] (q0) ..controls (45.436bp,27.27bp) and (58.635bp,31.898bp)  .. node[auto] {{}} (q1);
+  \draw [->] (q1) ..controls (121.23bp,55.953bp) and (131.02bp,58.496bp)  .. (140bp,57bp) .. controls (143.13bp,56.478bp) and (146.36bp,55.711bp)  .. node[auto] {$a$} (q2);
+  \draw [->] (q4) ..controls (361.28bp,28.238bp) and (374.94bp,33.562bp)  .. node[auto] {{}} (q5);
+%
+\end{tikzpicture}
+
+%%% end ex3p1 %%%
+}
+\end{center}
+
+Cet automate n'est pas déterministe : un automate comportant des
+ε-transitions est forcément non-déterministe.
+
+(2) Tous les états autres que $0$ (car il est initial) et $2,6,8,11$
+(car des transitions non spontanées y aboutissent) vont disparaître ;
+les ε-fermetures $C(q)$ de ces états sont les suivantes :
+
+\begin{center}
+\begin{tabular}{r|l}
+$q$&ε-fermeture $C(q)$\\
+\hline
+$0$&$\{0,1,3,4,5,13\}$\\
+$2$&$\{2,3,4,5,13\}$\\
+$6$&$\{6,7\}$\\
+$8$&$\{5,8,9,10,12,13\}$\\
+$11$&$\{5,10,11,12,13\}$\\
+\end{tabular}
+\end{center}
+
+En remplaçant chaque transition $q^\sharp \to q'$ étiquetée par $x$
+dans l'automate par une transition $q\to q'$ pour chaque état $q$ tel
+que $q^\sharp \in C(q)$, on obtient le NFA suivant :
+
+\begin{center}
+%%% begin ex3p1b %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q0) at (18bp,31.498bp) [draw,circle,state,initial,final,accepting below] {$0$};
+  \node (q2) at (97bp,61.498bp) [draw,circle,state,final] {$2$};
+  \node (q11) at (335.5bp,19.498bp) [draw,circle,state,final,accepting below] {$11$};
+  \node (q8) at (255bp,49.498bp) [draw,circle,state,final,accepting above] {$8$};
+  \node (q6) at (176bp,31.498bp) [draw,circle,state] {$6$};
+  \draw [->] (q0) ..controls (45.279bp,41.737bp) and (58.943bp,47.06bp)  .. node[auto] {$a$} (q2);
+  \draw [->] (q2) to[loop above] node[auto] {$a$} (q2);
+  \draw [->] (q8) ..controls (282.44bp,39.394bp) and (295.8bp,34.29bp)  .. node[auto] {$a$} (q11);
+  \draw [->] (q11) to[loop above] node[auto] {$a$} (q11);
+  \draw [->] (q11) ..controls (297.15bp,8.7001bp) and (264.63bp,2.1768bp)  .. (237bp,7.4983bp) .. controls (224.85bp,9.8374bp) and (212.04bp,14.613bp)  .. node[auto,near start] {$b$} (q6);
+  \draw [->] (q0) ..controls (47.643bp,24.415bp) and (64.2bp,20.964bp)  .. (79bp,19.498bp) .. controls (94.922bp,17.922bp) and (99.078bp,17.922bp)  .. (115bp,19.498bp) .. controls (125.98bp,20.586bp) and (137.94bp,22.768bp)  .. node[auto,below] {$b$} (q6);
+  \draw [->] (q2) ..controls (124.28bp,51.26bp) and (137.94bp,45.936bp)  .. node[auto] {$b$} (q6);
+  \draw [->] (q8) ..controls (234.03bp,34.749bp) and (226.51bp,30.579bp)  .. (219bp,28.498bp) .. controls (214.15bp,27.154bp) and (208.87bp,26.751bp)  .. node[auto,near start] {$b$} (q6);
+  \draw [->] (q6) ..controls (198.21bp,42.911bp) and (205.25bp,45.859bp)  .. (212bp,47.498bp) .. controls (216.59bp,48.613bp) and (221.55bp,49.292bp)  .. node[auto] {$a$} (q8);
+%
+\end{tikzpicture}
+
+%%% end ex3p1b %%%
+\end{center}
+
+Les états $0,2,8,11$ sont finaux car ce sont eux qui ont $13$ dans
+leur ε-fermeture.
+
+(3) L'automate ainsi obtenu est déjà déterministe incomplet ; pour le
+déterminiser-compléter, il n'y a qu'à ajouter un puits $\bot$ avec la
+seule transition qui manque, c'est-à-dire une transition étiquetée par
+$b$ depuis l'état $6$ (et des transitions de $\bot$ vers lui-même
+étiquetées $a$ et $b$).  Nous ne représentons pas l'automate à $6$
+états ainsi fabriqué.
+
+(4) On part de l'algorithme déterministe complet obtenu à la
+question (3), et on lui applique l'algorithme de minimisation.  On
+sépare d'abord ses états en deux classes, les finaux $\{0,2,8,11\}$ et
+les non-finaux $\{6,\bot\}$.  La transition étiquetée $a$ sépare les
+états $6$ et $\bot$ car le premier aboutit dans la classe
+$\{0,2,8,11\}$ tandis que le second aboutit dans la classe
+$\{6,\bot\}$.  On vérifie ensuite qu'aucune transition ne sépare des
+états.  L'automate minimal est donc le suivant :
+\begin{center}
+%%% begin ex3p1c %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q6) at (97bp,20.28bp) [draw,circle,state] {$6$};
+  \node (qbot) at (176bp,20.28bp) [draw,circle,state] {$\bot$};
+  \node (qF) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$F$};
+  \draw [->] (q6) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$a$} (qF);
+  \draw [->] (q6) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$b$} (qbot);
+  \draw [->] (qbot) to[loop above] node[auto] {$a,b$} (qbot);
+  \draw [->] (qF) to[loop above] node[auto] {$a$} (qF);
+  \draw [->] (qF) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$b$} (q6);
+%
+\end{tikzpicture}
+
+%%% end ex3p1c %%%
+\end{center}
+où l'état $F$ représente la classe $0\equiv 2\equiv 8\equiv 11$.
+
+(5) Il s'agit du langage constitué des mots n'ayant jamais deux $b$
+consécutifs, c'est-à-dire des mots dans lesquels chaque $b$ est suivi
+d'au moins un $a$ : l'expression rationnelle initiale le présente
+comme le langage constitués des mots formés d'un nombre quelconque de
+$a$ puis d'un nombre quelconque de répétitions d'un $b$ suivi d'au
+moins un $a$.  L'automate final interdit les suites de deux $b$
+consécutifs comme ceci : l'état $F$ correspond à la situation où on ne
+vient pas de rencontrer un $b$ (=la lettre précédente était un $a$ ou
+bien on vient de commencer le mot) et on n'en a jamais rencontré deux,
+l'état $6$ à la situation où on vient de rencontrer un $b$ et on n'en
+a jamais rencontré deux, et l'état $\bot$ à la situation où on a
+rencontré au moins une fois deux $b$ consécutifs.  Avec cette
+description, il est clair que l'automate fait ce qui était demandé.
+\end{corrige}
+
+
+
+%
+%
+%
+
+\bigbreak
+\centerline{\textbf{Calculabilité}}
+
 \exercice
 
 (1) Soit $\Sigma$ un alphabet (i.e., un ensemble fini).  L'ensemble $L
diff --git a/figs/ex3p1.dot b/figs/ex3p1.dot
new file mode 100644
index 0000000..2246f6f
--- /dev/null
+++ b/figs/ex3p1.dot
@@ -0,0 +1,38 @@
+digraph ex3p1 {
+	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",label="7"];
+	q8 [style="state",label="8"];
+	q9 [style="state",label="9"];
+	q10 [style="state",label="10"];
+	q11 [style="state",label="11"];
+	q12 [style="state",label="12"];
+	q13 [style="state,final",label="13"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q1 [label="e",texlbl="{}"];
+	q1 -> q2 [label="a"];
+	q2 -> q3 [label="e",texlbl="{}"];
+	q2 -> q1 [label="e",texlbl="{}"];
+	q0 -> q3 [label="e",texlbl="{}"];
+	q3 -> q4 [label="e",texlbl="{}"];
+	q4 -> q5 [label="e",texlbl="{}"];
+	q5 -> q6 [label="b"];
+	q6 -> q7 [label="e",texlbl="{}"];
+	q7 -> q8 [label="a"];
+	q8 -> q9 [label="e",texlbl="{}"];
+	q9 -> q10 [label="e",texlbl="{}"];
+	q10 -> q11 [label="a"];
+	q11 -> q12 [label="e",texlbl="{}"];
+	q11 -> q10 [label="e",texlbl="{}"];
+	q9 -> q12 [label="e",texlbl="{}"];
+	q12 -> q13 [label="e",texlbl="{}"];
+	q12 -> q5 [label="e",texlbl="{}"];
+	q4 -> q13 [label="e",texlbl="{}"];
+}
diff --git a/figs/ex3p1b.dot b/figs/ex3p1b.dot
new file mode 100644
index 0000000..cce02d8
--- /dev/null
+++ b/figs/ex3p1b.dot
@@ -0,0 +1,19 @@
+digraph ex3p1b {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q0 [style="state,initial,final,accepting below",label="0"];
+	q2 [style="state,final",label="2"];
+	q6 [style="state",label="6"];
+	q8 [style="state,final,accepting above",label="8"];
+	q11 [style="state,final,accepting below",label="11"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q2 [label="a"];
+	q2 -> q2 [label="a",topath="loop above"];
+	q2 -> q6 [label="b"];
+	q0 -> q6 [label="b",lblstyle="auto,below"];
+	q6 -> q8 [label="a"];
+	q8 -> q11 [label="a"];
+	q11 -> q11 [label="a",topath="loop above"];
+	q8 -> q6 [label="b",lblstyle="auto,near start"];
+	q11 -> q6 [label="b",lblstyle="auto,near start"];
+}
diff --git a/figs/ex3p1c.dot b/figs/ex3p1c.dot
new file mode 100644
index 0000000..c86eee0
--- /dev/null
+++ b/figs/ex3p1c.dot
@@ -0,0 +1,13 @@
+digraph ex3p1c {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	qF [style="state,initial,final,accepting below",label="F"];
+	q6 [style="state",label="6"];
+	qbot [style="state",label="X",texlbl="$\bot$"];
+	edge [texmode="math",lblstyle="auto"];
+	qF -> q6 [label="b"];
+	qF -> qF [label="a",topath="loop above"];
+	q6 -> qF [label="a"];
+	q6 -> qbot [label="b"];
+	qbot -> qbot [label="a,b",topath="loop above"];
+}