diff options
| -rw-r--r-- | controle-20180322.tex | 180 |
1 files changed, 179 insertions, 1 deletions
diff --git a/controle-20180322.tex b/controle-20180322.tex index 4d3f6fa..8ecc787 100644 --- a/controle-20180322.tex +++ b/controle-20180322.tex @@ -26,7 +26,7 @@ \newcommand\thingy{% \refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } \newcommand\exercice{% -\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}} +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} \renewcommand{\qedsymbol}{\smiley} % \DeclareUnicodeCharacter{00A0}{~} @@ -134,18 +134,196 @@ L$). spontanée, $\mathscr{A}_1$ qui reconnaît le langage $L$. On justifiera rapidement pourquoi l'automate proposé convient. +\begin{corrige} +On peut proposer l'automate $\mathscr{A}_1$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (140bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3$}; +\draw [->] (q0) to[loop below] node[auto] {$a,b,c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a,b,c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a,b,c$} (q2); +\draw [->] (q2) -- node[auto] {$c$} (q3); +\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3); +\end{tikzpicture} +\end{center} +Pour se convaincre qu'il convient, on remarque qu'un chemin de +l'unique état initial ($0$) à l'unique état final ($3$) dans cet +automate est formé par trois transitions $0\to 1$, $1\to 2$ et $2\to +3$, étiquetées par les lettres $a$, $b$ et $c$ respectivement, +intercalées d'un nombre quelconque de transitions d'un état vers +lui-même, étiquetées par une lettre quelconque : la lecture de ses +étiquettes donne bien un mot ayant $abc$ comme sous-mot ; et +réciproquement, tout tel mot étiquette au moins un chemin de $0$ à $3$ +(une fois choisies les lettres $a,b,c$ dans l'ordre qui correspondront +aux transitions changeant d'état). + +\emph{Remarque :} il est correct de donner directement l'automate +déterministe $\mathscr{A}_2$ représenté ci-dessous (puisque tout NFA +est, en particulier, un DFA), à condition de justifier proprement +qu'il convient. +\end{corrige} + (2) Déterminiser (si nécessaire) l'automate $\mathscr{A}_1$ trouvé en (1) ; on appellera $\mathscr{A}_2$ l'automate résultant. +\begin{corrige} +En notant $0':=\{0\}$, $1' := \{0,1\}$, $2' := \{0,1,2\}$ et $3' := +\{0,1,2,3\}$ les états de l'automate déterministe $\mathscr{A}_2$ qui +correspondent aux ensembles d'états de l'automate $\mathscr{A}_1$ +qu'on vient d'indiquer, la déterminisation conduit à l'automate +$\mathscr{A}_1$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$}; +\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$}; +\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3'$}; +\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2); +\draw [->] (q2) -- node[auto] {$c$} (q3); +\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + (3) Minimiser (si nécessaire) l'automate $\mathscr{A}_2$ obtenu en (2) ; on appellera $\mathscr{A}_3$ l'automate minimal (=canonique) résultant. +\begin{corrige} +On part bien d'un automate $\mathscr{A}_2$ déterministe complet sans +état inaccessible. La première étape de l'algorithme de minimisation +sépare deux classes d'états : $0',1',2'$ (non finaux) d'une part et +$3'$ (finaux) de l'autre. Ensuite on sépare $0',1'$ d'une part et +$2'$ de l'autre (car les premiers ne conduisent qu'à des états non +finaux, tandis que $2'$ conduit à un état final par la transition +étiquetée $c$). L'étape suivante sépare $0'$ et $1'$ (car le premier +ne conduit qu'à un état de la classe $0',1'$ de l'étape précédente, +tandis que $1'$ conduit à un état de la classe $2'$ par la transition +étiquetée $b$). On a donc séparé tous les états, ce qui montre que +$\mathscr{A}_3 = \mathscr{A}_2$ est minimal. + +\emph{Remarque :} on pouvait aussi invoquer l'argument suivant : +puisque le mot $abc$ doit être accepté et qu'aucun de ses sous-mots +stricts ne l'est (ce qui exclut qu'il y ait une boucle dans le chemin +d'acceptation), il faut au moins $|abc|+1 = 4$ états dans n'importe +quel automate reconnaissant $L$. Comme $\mathscr{A}_2$ a +effectivement $4$ états, il est forcément minimal. +\end{corrige} + (4) Construire un automate $\mathscr{A}_4$ reconnaissant le langage $M := \Sigma^*\setminus L$ complémentaire de $L$. +\begin{corrige} +On obtient $\mathscr{A}_4$ en échangeant états finaux et non finaux +dans $\mathscr{A}_3 = \mathscr{A}_2$, c'est-à-dire l'automate +$\mathscr{A}_3$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state,final,accepting above] {$1'$}; +\node (q2) at (140bp,0bp) [draw,circle,state,final,accepting above] {$2'$}; +\node (q3) at (210bp,0bp) [draw,circle,state] {$3'$}; +\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2); +\draw [->] (q2) -- node[auto] {$c$} (q3); +\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + (5) En appliquant à $\mathscr{A}_4$ la méthode d'élimination des états, déterminer une expression rationnelle dénotant le langage $M$. +(Si on souhaite obtenir une expression plus compacte, il est +recommandé de commencer l'élimination des états par ceux qui sont +plutôt proches de l'état final.) + +\begin{corrige} +On va manipuler des automates finis à transitions étiquetées par des +expressions rationnelles (ou « RNFA »). Dans un premier temps, on +donne à l'automate un unique état final $F$ en faisant pointer vers +lui une transition spontanée (i.e., étiquetée +par $\underline{\varepsilon}$) depuis tout état qui était final, et un +unique état initial $I$ depuis lequel on fait partir une transition +spontanée vers $0$. L'état $3'$ peut être éliminé d'emblée puisqu'il +est inutile (il n'est pas co-accessible : c'est un puits !). Par +ailleurs, deux transitions entre les mêmes états sont remplacées par +une seule étiquetée par la disjonction des étiquettes (par exemple, +les deux transitions $0'\to 0'$ étiquetées $b,c$ sont remplacées par +une seule étiquetée $b|c$). On a donc affaire à l'automate suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$}; +\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$}; +\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$}; +\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0); +\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a|b$} (q2); +\draw [->] (q2) -- node[auto] {$\underline{\varepsilon}$} (qF); +\draw [->] (q1) to[out=45,in=135] node[auto] {$\underline{\varepsilon}$} (qF); +\draw [->] (q0) to[out=90,in=180] (70bp,60bp) to node[auto] {$\underline{\varepsilon}$} (140bp,60bp) to[out=0,in=90] (qF); +\end{tikzpicture} +\end{center} +On élimine maintenant l'état $2'$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$}; +\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$}; +\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0); +\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1); +\draw [->] (q1) -- node[auto] {$\underline{\varepsilon}|b(a|b){*}$} (qF); +\draw [->] (q0) to[out=90,in=180] (70bp,40bp) to node[auto] {$\underline{\varepsilon}$} (140bp,40bp) to[out=0,in=90] (qF); +\end{tikzpicture} +\end{center} +(on a fait usage du fait évident que l'expression rationnelle +$r\underline{\varepsilon}$ est équivalente à $r$). On élimine +ensuite l'état $1'$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$}; +\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$}; +\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0); +\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0); +\draw [->] (q0) -- node[auto] {$\underline{\varepsilon}|a(a|c){*}(\underline{\varepsilon}|b(a|b){*})$} (qF); +\end{tikzpicture} +\end{center} +Enfin, l'élimination de l'état $0'$ conduit au RNFA ayant seulement +deux états $I$ et $F$ reliés par une transition étiquetée par +\[ +(b|c){*}\Big(\underline{\varepsilon}|a(a|c){*}\big(\underline{\varepsilon}|b(a|b){*}\big)\Big) +\] +qui est l'expression rationnelle recherchée (dénotant $M$). + +L'élimination des états dans l'ordre $0',1',2'$ conduirait à +l'expression rationnelle moins compacte +\[ +\underline{\varepsilon}\;|\;(b|c){*}\;|\;(b|c){*}a(a|c){*}\;|\;(b|c){*}a(a|c){*}b(a|b){*} +\] +qui est cependant sans doute plus lisible. +\end{corrige} % |