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}
+
+
 
 %
 %