diff options
| -rw-r--r-- | controle-20170207.tex | 183 |
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} |