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