summaryrefslogtreecommitdiffstats
path: root/exercices3.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-27 17:36:19 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-27 17:36:19 (GMT)
commit16db49ec807cca5e201243d35b16eed028d03ae8 (patch)
tree838f7478ab7532e5065d9d08d48bc76b6ae1a494 /exercices3.tex
parent64deabcf51fe764a0787d200512a0e5c59c68140 (diff)
downloadinf105-16db49ec807cca5e201243d35b16eed028d03ae8.zip
inf105-16db49ec807cca5e201243d35b16eed028d03ae8.tar.gz
inf105-16db49ec807cca5e201243d35b16eed028d03ae8.tar.bz2
An exercise on finite automata.
Diffstat (limited to 'exercices3.tex')
-rw-r--r--exercices3.tex181
1 files changed, 181 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