diff options
| -rw-r--r-- | controle-20210618.tex | 147 |
1 files changed, 147 insertions, 0 deletions
diff --git a/controle-20210618.tex b/controle-20210618.tex index a2bf362..ea91ea0 100644 --- a/controle-20210618.tex +++ b/controle-20210618.tex @@ -135,6 +135,11 @@ immédiatement suivis par la lettre $a$, puis n'importe quoi). $a$, $b$, $ab$, $ba$, $bb$, $bab$, $bba$, $baba$. On ne demande pas de justifier les réponses. +\begin{corrige} +Les mots $\varepsilon$, $a$, $b$, $ab$ et $bb$ n'appartiennent pas +à $L$ ; les mots $ba$, $bab$, $bba$ et $baba$ appartiennent à $L$. +\end{corrige} + \emph{Il est fortement conseillé, dans toutes les questions suivantes, d'utiliser les mots qui viennent d'être listés pour vérifier les automates successifs qu'on calculera.} (Par exemple, pour un @@ -155,22 +160,164 @@ l'automate ainsi obtenu. À défaut de donner l'automate de Glushkov ou de Thompson, donner un NFA reconnaissant $L$ pourra apporter une partie des points.) +\begin{corrige} +L'automate $\mathscr{A}_1$ trouvé est le suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$}; +\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$}; +\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$a$} (q4); +\draw[->] (q3) -- node[auto,below]{$b$} (q5); +\draw[->] (q4) to[loop above] node[auto]{$a$} (q4); +\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5); +\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4); +\draw[->] (q5) to[loop below] node[auto]{$b$} (q5); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + (2) Déterminiser l'automate $\mathscr{A}_1$. On appellera $\mathscr{A}_2$ l'automate en question. On rappelle qu'on attend ici un automate fini \emph{déterministe complet}. +\begin{corrige} +L'automate $\mathscr{A}_1$ est déjà déterministe, mais incomplet : +pour le transformer en automate déterministe complet, on se contente +de lui ajouter un puits pour obtenir l'automate $\mathscr{A}_2$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$}; +\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$}; +\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$}; +\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$a$} (q4); +\draw[->] (q3) -- node[auto,below]{$b$} (q5); +\draw[->] (q4) to[loop above] node[auto]{$a$} (q4); +\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5); +\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4); +\draw[->] (q5) to[loop below] node[auto]{$b$} (q5); +\draw[->] (q0) -- node[auto,swap]{$a$} (Sink); +\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + (3) Minimiser l'automate $\mathscr{A}_2$. On appellera $\mathscr{A}_3$ l'automate minimal ainsi obtenu (automate canonique du langage $L$). +\begin{corrige} +L'automate $\mathscr{A}_2$ est déterministe complet sans état +inaccessible. On commence l'algorithme de minimisation en séparant +les états finaux $\{3,4,5\}$ et non-finaux $\{0,1,2,\bot\}$. On +sépare ensuite ces derniers en deux classes, $\{1,2\}$ et $\{0,\bot\}$ +selon que la transition étiquetée $a$ conduit à un état final. Enfin, +la transition étiquetée $b$ sépare la classe $\{0,\bot\}$ en deux. +Finalement, on aboutit aux classes suivantes : $\{0\}$, $\{1,2\}$, +$\{3,4,5\}$ et $\{\bot\}$, et à l'automate minimal $\mathscr{A}_3$ +suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q3) at (120bp,0bp) [draw,circle,state,final] {$3$}; +\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3); +\draw[->] (q0) -- node[auto,swap]{$a$} (Sink); +\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + (4) Déduire de $\mathscr{A}_3$ un automate fini déterministe complet $\mathscr{A}_4$ reconnaissant le langage $M := \Sigma^*\setminus L$ complémentaire de $L$. +\begin{corrige} +Il suffit d'échanger les états finaux et non-finaux +dans $\mathscr{A}_3$, ce qui donne l'automate $\mathscr{A}_4$ +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 (60bp,0bp) [draw,circle,state,final,accepting below] {$1$}; +\node (q3) at (120bp,0bp) [draw,circle,state] {$3$}; +\node (qZ) at (0bp,-50bp) [draw,circle,final] {$Z$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3); +\draw[->] (q0) -- node[auto,swap]{$a$} (qZ); +\draw[->] (qZ) to[loop left] node[auto]{$a,b$} (qZ); +\end{tikzpicture} +\end{center} +(On a renommé l'état $\bot$ en $Z$ vu que ce n'est plus un puits sur +ce nouvel automate, en revanche $3$ en est un. Ces nom sont, bien +sûr, sans aucun impact sur le fonctionnement de l'automate.) +\end{corrige} + (5) En appliquant l'algorithme d'élimination des états, déduire de $\mathscr{A}_4$ une expression rationnelle $s$ dénotant le langage $M$ (c'est-à-dire vérifiée exactement par les mots qui ne vérifient pas $r$). +\begin{corrige} +Pour procéder à l'algorithme d'élimination des états, on commence par +donner à l'automate un unique état final sans aucune transition qui en +part, appelons-le $\infty$. On peut aussi d'ores et déjà éliminer +l'état $3$ qui est maintenant inutile : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (qZ) at (0bp,-50bp) [draw,circle] {$Z$}; +\node (final) at (60bp,-50bp) [draw,circle,final] {$\infty$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$b$} (q1); +\draw[->] (q0) -- node[auto,swap]{$a$} (qZ); +\draw[->] (qZ) to[loop left] node[auto]{$a,b$} (qZ); +\draw[->] (q0) -- node[auto]{$\varepsilon$} (final); +\draw[->] (q1) -- node[auto]{$\varepsilon$} (final); +\draw[->] (qZ) -- node[auto,below]{$\varepsilon$} (final); +\end{tikzpicture} +\end{center} +L'élimination de l'état $1$ conduit à remplacer la transition +$0\to\infty$ étiquetée $\varepsilon$ par $\varepsilon | bb{*}$, et +l'élimination de l'état $Z$ conduit à y ajouter $a(a|b){*}$. +Finalement, on a affaire à un automate ayant les seuls états $0$ +(initial) et $\infty$ (final) avec la seule transition $0\to\infty$ +étiquetée par l'expression rationnelle $s$ recherchée : +\[ +\varepsilon \,|\, bb{*} \,|\, a(a|b){*} +\] +qui dénote le langage $M$ complémentaire de $L$. (Autrement dit : un +mot qui \emph{n'est pas} un nombre $\geq 1$ de $b$ suivi d'un $a$ +suivi de n'importe quoi, c'est la même chose qu'un mot soit vide, soit +formé uniquement d'un nombre $\geq 1$ de $b$, soit d'un $a$ suivi de +n'importe quoi.) +\end{corrige} % |