diff options
Diffstat (limited to 'exercices3.tex')
| -rw-r--r-- | exercices3.tex | 181 |
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 |