More working with automaton.

1 files changed, 170 insertions, 13 deletions

diff --git a/controle-20170207.tex b/controle-20170207.tex
index 2035c6e..583053d 100644
--- a/controle-20170207.tex
+++ b/controle-20170207.tex
@@ -138,9 +138,9 @@ représenté par la figure suivante :
 (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.
+(1) Décrire brièvement, en français, le langage $L$ 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.)
@@ -152,21 +152,37 @@ correcteur, on demande de faire en sorte que les transitions
 la gauche vers la droite, et celles étiquetées par $b$, verticales du
 haut vers le bas.
 
+(4) Minimiser l'automate ainsi obtenu, si nécessaire.
+
+(5) Donner un automate du type qu'on voudra qui reconnaît le langage
+$\overline{L} = \Sigma^*\setminus L$ complémentaire de $L$.
+
+(6) Décrire brièvement, en français, le langage ce langage
+complémentaire $\overline{L}$.
+
+(7) Donner une expression rationnelle qui reconnaît ce langage
+complémentaire $\overline{L}$.  (Cette question est plus difficile.
+Ne pas hésiter à introduire des notations intermédiaires.)
+
 \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{*}$.
+\smallbreak
+
+(1) Le chemin par les états $X,A,A',Y$ accepte les mots exactement
+un $a$, c'est-à-dire le langage dénoté par $b{*}ab{*}$.  Le chemin par
+les états $X,B,B',Y$ accepte les mots comportant exactement un $b$,
+c'est-à-dire le langage dénoté par $a{*}ba{*}$.  L'automate dans son
+ensemble accepte les mots comportant exactement un $a$ ou (inclusif)
+exactement un $b$ (i.e. $L = \{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{*}$.
+
+\smallbreak
 
 (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\}$ ;
@@ -195,6 +211,8 @@ haut vers le bas.
 (On a supprimé l'état $Y$ qui est devenu inutile car aucune transition
 non-spontanée n'y conduit.)
 
+\smallbreak
+
 (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 :
@@ -229,6 +247,145 @@ entourant deux fois plutôt que par une flèche sortante :
 \draw[->] (s22) to[loop below] node[auto]{$b$} (s22);
 \end{tikzpicture}
 \end{center}
+
+Pour la commodité de la suite de la correction, on renomme les états
+de cet automate de la façon suivante :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$};
+\node (s01) at (75bp,0bp) [draw,rounded corners,state,accepting by double] {$01$};
+\node (s02) at (150bp,0bp) [draw,rounded corners,state] {$02$};
+\node (s10) at (0bp,-50bp) [draw,rounded corners,state,accepting by double] {$10$};
+\node (s11) at (75bp,-50bp) [draw,rounded corners,state,accepting by double] {$11$};
+\node (s12) at (150bp,-50bp) [draw,rounded corners,state,accepting by double] {$12$};
+\node (s20) at (0bp,-100bp) [draw,rounded corners,state] {$20$};
+\node (s21) at (75bp,-100bp) [draw,rounded corners,state,accepting by double] {$21$};
+\node (s22) at (150bp,-100bp) [draw,rounded corners,state] {$22$};
+\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}
+
+\smallbreak
+
+(4) L'automate obtenu est déjà minimal.  En effet, l'algorithme de
+minimisation commence par séparer les classes $\{01,10,11,12,21\}$
+(états finaux) et $\{00,02,20,22\}$ (états non-finaux) ; ensuite, la
+transition étiquetée par $a$ sépare la classe $\{01,10,11,12,21\}$ en
+$\{01,21\}$ (qui vont vers un état non-final) et $\{10,11,12\}$ (qui
+vont vers un état final), et la classe $\{00,02,20,22\}$ en
+$\{00,20\}$ (qui vont vers un état final) et $\{02,22\}$ (qui vont
+vers un non-final).  La transition étiquetée par $b$ sépare ensuite en
+deux chacune des trois classes $\{00,20\}$, $\{01,21\}$ et $\{02,22\}$
+(car le premier élément va dans la classe $\{10,11,12\}$ tandis que le
+second reste dans la même classe) et sépare en trois la classe
+$\{10,11,12\}$.  On a donc séparé chacun des états.
+
+\smallbreak
+
+(5) Pour reconnaître le complémentaire du langage reconnu par un
+automate fini déterministe complet, il suffit d'échanger états finaux
+et non-finaux : on peut donc prendre l'automate dessiné en (3) avec,
+cette fois, la convention que les états simplement entourés sont
+finaux (et les doublement entourés sont non-finaux).
+
+\emph{Attention :} échanger états finaux et non-finaux ne marche pas
+pour reconnaître le complémentaire du langage reconnu par un automate
+non-déterministe (car la négation de « il existe un chemin qui va vers
+un état final » est « aucun chemin ne va vers un état final » et pas
+« il existe un chemin qui va vers un état non-final »).
+
+\smallbreak
+
+(6) Puisque $L$ est le langage formé des mots ayant comportant
+exactement un $a$ ou (inclusif) exactement un $b$, son complémentaire
+$\overline{L}$ est formé des mots ayant un nombre différent de $1$
+de $a$ \emph{et} un nombre différent de $1$ de $b$ ; si on préfère, il
+s'agit du langage comportant ($0$ ou au moins $2$ fois la lettre $a$)
+\emph{et} ($0$ ou au moins $2$ fois la lettre $b$).
+
+\smallbreak
+
+(7) L'élimination des états n'est pas trop complexe car l'automate a
+très peu de boucles.  Éliminons simultanément tous les états
+non-finaux ($01$, $10$, $11$, $12$ et $21$), et profitons-en pour
+créer un nouvel (et unique) état final $F$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$};
+\node (s02) at (100bp,0bp) [draw,rounded corners,state] {$02$};
+\node (s20) at (0bp,-60bp) [draw,rounded corners,state] {$20$};
+\node (s22) at (100bp,-60bp) [draw,rounded corners,state] {$22$};
+\node (F) at (160bp,-60bp) [draw,circle,state,final] {$F$};
+\draw[->] (s00) -- node[auto]{$aa$} (s02);
+\draw[->] (s20) -- node[auto]{$ab{*}a$} (s22);
+\draw[->] (s02) to[loop above] node[auto]{$a$} (s02);
+\draw[->] (s00) -- node[auto]{$bb$} (s20);
+\draw[->] (s02) -- node[auto]{$ba{*}b$} (s22);
+\draw[->] (s20) to[loop left] node[auto]{$b$} (s20);
+\draw[->] (s22) to[loop below] node[auto]{$a|b$} (s22);
+\draw[->] (s22) -- node[auto]{$\varepsilon$} (F);
+\draw[->] (s00) -- node[auto]{$r$} (s22);
+\draw[->,out=0,in=90] (s02) to node[auto]{$\varepsilon$} (F);
+\draw[->,out=270,in=270] (s20) to node[auto,below]{$\varepsilon$} (F);
+\draw[->] (s00) to[out=45,in=180] (100bp,40bp) to[out=0,in=45] node[auto,above]{$\varepsilon$} (F);
+\end{tikzpicture}
+\end{center}
+où $r := abaa{*}b \,|\, abbb{*}a \,|\, baaa{*}b \,|\, babb{*}a$
+(correspondant aux quatre façons de passer de $00$ à $22$ dans le
+graphe ci-dessus).  Éliminons l'état $02$ et l'état $20$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$};
+\node (s22) at (100bp,-60bp) [draw,rounded corners,state] {$22$};
+\node (F) at (160bp,-60bp) [draw,circle,state,final] {$F$};
+\draw[->] (s22) -- node[auto]{$\varepsilon$} (F);
+\draw[->] (s22) to[loop above] node[auto]{$a|b$} (s22);
+\draw[->] (s00) -- node[auto]{$r'$} (s22);
+\draw[->,out=0,in=90] (s00) to node[auto]{$\varepsilon|aaa{*}|bbb{*}$} (F);
+\end{tikzpicture}
+\end{center}
+où $r' := r \penalty0\,|\, aaa{*}ba{*}b \penalty0\,|\, bbb{*}ab{*}a =
+abaa{*}b \penalty0\,|\, abbb{*}a \penalty0\,|\, baaa{*}b
+\penalty0\,|\, babb{*}a \penalty0\,|\, aaa{*}ba{*}b \penalty0\,|\,
+bbb{*}ab{*}a$.  On obtient finalement l'expression rationnelle
+suivante pour $\overline{L}$ :
+\[
+\varepsilon\,|\,aaa{*}\,|\,bbb{*}\,|\,(abaa{*}b \,|\,
+abbb{*}a \,|\, baaa{*}b \,|\, babb{*}a
+\,|\, aaa{*}ba{*}b \,|\, bbb{*}ab{*}a)(a|b){*}
+\]
+Pour comprendre cette expression rationnelle, la disjonction de plus
+haut niveau correspond aux quatre possibilités : (i) $0$ fois la
+lettre $a$ et $0$ fois la lettre $b$, (ii) au moins $2$ fois la lettre
+$a$ et $0$ fois la lettre $b$, (iii) $0$ fois la lettre $a$ et au
+moins $2$ fois la lettre $b$, et (iv) au moins $2$ fois la lettre $a$
+et au moins $2$ fois la lettre $b$.  Pour mieux comprendre
+l'expression du cas (iv), on peut remarquer que $abaa{*}b
+\penalty0\,|\, baaa{*}b \penalty0\,|\, aaa{*}ba{*}b$ dénote le langage
+formé des mots comportant au moins deux $a$ et exactement deux $b$ et
+qui finissent par un $b$, et symétriquement $abbb{*}a \penalty0\,|\,
+babb{*}a \penalty0\,|\,bbb{*}ab{*}a$ dénote le langage formé des mots
+comportant au moins deux $b$ et exactement deux $a$ et qui finissent
+par un $a$ : l'expression du cas (iv) correspond donc à écrire un mot
+ayant au moins deux $a$ et au moins deux $b$ comme le premier préfixe
+qui vérifie cette propriété suivi d'un suffixe quelconque.
 \end{corrige}