diff options
| -rw-r--r-- | controle-20170207.tex | 126 |
1 files changed, 126 insertions, 0 deletions
diff --git a/controle-20170207.tex b/controle-20170207.tex index e32497e..2035c6e 100644 --- a/controle-20170207.tex +++ b/controle-20170207.tex @@ -106,6 +106,132 @@ Durée : 1h30 \pagebreak +% +% +% + +\exercice + +On considère l'automate fini sur l'alphabet $\Sigma = \{a,b\}$ +représenté par la figure suivante : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$}; +\node (Y) at (80bp,0bp) [draw,circle,state,final] {$Y$}; +\node (A1) at (-40bp,50bp) [draw,circle,state] {$A$}; +\node (A2) at (40bp,50bp) [draw,circle,state] {$A'$}; +\node (B1) at (-40bp,-50bp) [draw,circle,state] {$B$}; +\node (B2) at (40bp,-50bp) [draw,circle,state] {$B'$}; +\draw[->] (X) -- node[auto]{$\varepsilon$} (A1); +\draw[->] (X) -- node[auto,below left]{$\varepsilon$} (B1); +\draw[->] (A1) -- node[auto]{$a$} (A2); +\draw[->] (B1) -- node[auto]{$b$} (B2); +\draw[->] (A1) to[loop above] node[auto]{$b$} (A1); +\draw[->] (A2) to[loop above] node[auto]{$b$} (A2); +\draw[->] (B1) to[loop below] node[auto]{$a$} (B1); +\draw[->] (B2) to[loop below] node[auto]{$a$} (B2); +\draw[->] (A2) -- node[auto]{$\varepsilon$} (Y); +\draw[->] (B2) -- node[auto,below right]{$\varepsilon$} (Y); +\end{tikzpicture} +\end{center} + +(0) De quelle sorte d'automate s'agit-il ? (Autrement dit : est-il +déterministe ou non ? avec transitions spontanées ou non ?) + +(1) Décrire brièvement, en français, le langage reconnu (=accepté) par +l'automate en question, puis donner une expression rationnelle qui le +dénote. + +(2) Éliminer les transitions spontanées de l'automate, s'il y en a. +(On supprimera les états devenus inutiles.) + +(3) Déterminiser l'automate ainsi obtenu, si nécessaire. (On demande +un automate déterministe complet.) Pour simplifier le travail du +correcteur, on demande de faire en sorte que les transitions +étiquetées par $a$ soient, dans la mesure du possible, horizontales de +la gauche vers la droite, et celles étiquetées par $b$, verticales du +haut vers le bas. + +\begin{corrige} +(0) Il s'agit d'un automate non-déterministe à transitions spontanées, + ou ε-NFA (il n'y a pas de notion d'automate déterministe à + transitions spontanées). + +(1) Le chemin par les états $X,A,A',Y$ accepte les mots comportant un + et un seul $a$, c'est-à-dire le langage dénoté par $b{*}ab{*}$. Le + chemin par les états $X,B,B',Y$ accepte les mots comportant un et un + seul $b$, c'est-à-dire le langage dénoté par $a{*}ba{*}$. + L'automate dans son ensemble accepte les mots comportant soit un + unique $a$, soit un unique $b$ (i.e. $\{w\in\Sigma^* : |w|_a = 1 + \penalty0\ \textrm{ou}\penalty0\ |w|_b = 1\}$ si $|w|_x$ désigne le + nombre total d'occurrences de la lettre $x$ dans le mot $w$). C'est + le langage dénoté par l'expression rationnelle $b{*}ab{*} | + a{*}ba{*}$. + +(2) La ε-fermeture de l'état $X$ est $\{X,A,B\}$ ; la ε-fermeture de + l'état $A'$ est $\{A',Y\}$ et celle de l'état $B'$ est $\{B',Y\}$ ; + les autres états sont leur propre ε-fermeture (i.e., celle-ci est un + singleton). L'élimination des transitions spontanées conduit donc à + l'automate suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$}; +\node (A1) at (-40bp,50bp) [draw,circle,state] {$A$}; +\node (A2) at (40bp,50bp) [draw,circle,state,final] {$A'$}; +\node (B1) at (-40bp,-50bp) [draw,circle,state] {$B$}; +\node (B2) at (40bp,-50bp) [draw,circle,state,final] {$B'$}; +\draw[->] (X) -- node[auto]{$b$} (A1); +\draw[->] (X) -- node[auto,below left]{$a$} (B1); +\draw[->] (X) -- node[auto,below right]{$a$} (A2); +\draw[->] (X) -- node[auto,above right]{$b$} (B2); +\draw[->] (A1) -- node[auto]{$a$} (A2); +\draw[->] (B1) -- node[auto]{$b$} (B2); +\draw[->] (A1) to[loop above] node[auto]{$b$} (A1); +\draw[->] (A2) to[loop above] node[auto]{$b$} (A2); +\draw[->] (B1) to[loop below] node[auto]{$a$} (B1); +\draw[->] (B2) to[loop below] node[auto]{$a$} (B2); +\end{tikzpicture} +\end{center} +(On a supprimé l'état $Y$ qui est devenu inutile car aucune transition +non-spontanée n'y conduit.) + +(3) L'algorithme de déterminisation conduit à l'automate suivant où, +pour plus de lisibilité, les états finaux ont été marqués en les +entourant deux fois plutôt que par une flèche sortante : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$\{X\}$}; +\node (s01) at (75bp,0bp) [draw,rounded corners,state,accepting by double] {$\{A',B\}$}; +\node (s02) at (150bp,0bp) [draw,rounded corners,state] {$\{B\}$}; +\node (s10) at (0bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{A,B'\}$}; +\node (s11) at (75bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{A',B'\}$}; +\node (s12) at (150bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{B'\}$}; +\node (s20) at (0bp,-100bp) [draw,rounded corners,state] {$\{A\}$}; +\node (s21) at (75bp,-100bp) [draw,rounded corners,state,accepting by double] {$\{A'\}$}; +\node (s22) at (150bp,-100bp) [draw,rounded corners,state] {$\varnothing$}; +\draw[->] (s00) -- node[auto]{$a$} (s01); +\draw[->] (s01) -- node[auto]{$a$} (s02); +\draw[->] (s10) -- node[auto]{$a$} (s11); +\draw[->] (s11) -- node[auto]{$a$} (s12); +\draw[->] (s20) -- node[auto]{$a$} (s21); +\draw[->] (s21) -- node[auto]{$a$} (s22); +\draw[->] (s02) to[loop right] node[auto]{$a$} (s02); +\draw[->] (s12) to[loop right] node[auto]{$a$} (s12); +\draw[->] (s22) to[loop right] node[auto]{$a$} (s22); +\draw[->] (s00) -- node[auto]{$b$} (s10); +\draw[->] (s10) -- node[auto]{$b$} (s20); +\draw[->] (s01) -- node[auto]{$b$} (s11); +\draw[->] (s11) -- node[auto]{$b$} (s21); +\draw[->] (s02) -- node[auto]{$b$} (s12); +\draw[->] (s12) -- node[auto]{$b$} (s22); +\draw[->] (s20) to[loop below] node[auto]{$b$} (s20); +\draw[->] (s21) to[loop below] node[auto]{$b$} (s21); +\draw[->] (s22) to[loop below] node[auto]{$b$} (s22); +\end{tikzpicture} +\end{center} +\end{corrige} + + % % |