diff options
| -rw-r--r-- | controle-20170207.tex | 166 |
1 files changed, 86 insertions, 80 deletions
diff --git a/controle-20170207.tex b/controle-20170207.tex index 1d42a3e..dae78cd 100644 --- a/controle-20170207.tex +++ b/controle-20170207.tex @@ -101,7 +101,7 @@ de traiter toutes les questions pour obtenir la totalité des points. L'usage de tous les documents (notes de cours manuscrites ou imprimées, feuilles d'exercices, livres) est autorisé. -L'usage des calculatrices électroniques est interdit. +L'usage des appareils électroniques est interdit. \medbreak @@ -118,7 +118,7 @@ L'énoncé comporte 4 pages (page de garde incluse) \exercice -On considère l'automate fini sur l'alphabet $\Sigma = \{a,b\}$ +On considère l'automate fini $M$ sur l'alphabet $\Sigma = \{a,b\}$ représenté par la figure suivante : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton] @@ -145,7 +145,7 @@ représenté par la figure suivante : déterministe ou non ? avec transitions spontanées ou non ?) (1a) Décrire brièvement, en français, le langage $L$ reconnu -(=accepté) par l'automate en question, puis donner une expression +(=accepté) par l'automate $M$, puis donner une expression rationnelle qui le dénote. (On pourra préférer traiter la question (1b) d'abord.) @@ -155,17 +155,21 @@ $\varepsilon$, $a$, $b$, $ab$, $aa$, $aab$, $aabb$, $abab$, $ababa$. rapidement les réponses aux questions suivantes et ainsi détecter d'éventuelles erreurs lors des transformations des automates.) -(2) Éliminer les transitions spontanées de l'automate. -(On supprimera les états devenus inutiles.) +(2) Éliminer les transitions spontanées de l'automate $M$. (On +supprimera les états devenus inutiles.) On appellera $M_2$ l'automate +obtenu. -(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. +(3) Déterminiser l'automate $M_2$ obtenu en (2), si nécessaire. (On +demande un automate déterministe complet.) On appellera $M_3$ +l'automate déterminisé. -(4) Minimiser l'automate ainsi obtenu, si nécessaire (justifier). +Pour simplifier le travail du correcteur, on demande de représenter +$M_3$ de 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. + +(4) Minimiser l'automate $M_3$ obtenu en (3), si nécessaire +(justifier). (5) Donner un automate (de n'importe quelle sorte) qui reconnaît le langage $\overline{L} = \Sigma^*\setminus L$ complémentaire de $L$. @@ -179,22 +183,23 @@ complémentaire $\overline{L}$. (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). +(0) L'automate $M$ est un automate fini non-déterministe à transitions + spontanées, ou ε-NFA (le concept d'« automate déterministe à + transitions spontanées » n'aurait tout simplement pas de sens). \smallbreak (1a) 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 +c'est-à-dire le langage dénoté par $a{*}ba{*}$. L'automate $M$ 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{*}$. +le langage dénoté par l'expression rationnelle $b{*}ab{*} | a{*}ba{*}$ +(nous notons ici et ailleurs $|$ pour la disjonction, qu'on peut aussi +noter $+$). (1b) Parmi les mots proposés, $a$, $b$, $ab$ et $aab$ appartiennent à $L$, tandis que $\varepsilon$, $aa$, $aabb$, $abab$ et $ababa$ n'y @@ -202,11 +207,11 @@ appartiennent pas. \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\}$ ; - 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 : +(2) La ε-fermeture (arrière) 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 $M_2$ suivant : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton] \node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$}; @@ -231,8 +236,8 @@ 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 +(3) L'algorithme de déterminisation conduit à l'automate $M_3$ 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] @@ -267,7 +272,7 @@ entourant deux fois plutôt que par une flèche sortante : \end{center} Pour la commodité de la suite de la correction, on renomme les états -de cet automate de la façon suivante : +de cet automate $M_3$ 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$}; @@ -307,7 +312,7 @@ lettre $b$. \smallbreak -(4) L'automate obtenu est déjà minimal. En effet, l'algorithme de +(4) L'automate $M_3$ 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 @@ -327,6 +332,7 @@ 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). +Appelons-le $M_5$. \emph{Attention :} échanger états finaux et non-finaux ne marche pas pour reconnaître le complémentaire du langage reconnu par un automate @@ -337,17 +343,17 @@ 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$). +(6) Puisque $L$ est le langage formé des mots 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 +(7) L'élimination des états n'est pas trop complexe car l'automate +$M_5$ 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} @@ -563,33 +569,33 @@ S &\rightarrow TS \;|\; \varepsilon\\ T &\rightarrow aSbSc\\ \end{aligned} \] -On notera $L(G) = L(G,S)$ le langage qu'elle engendre, et $L(G,T)$ le +On notera $L(S) = L_G$ le langage qu'elle engendre, et $L(T)$ le langage des mots qui dérivent de $T$ (c'est-à-dire, si on préfère, le langage engendré par la grammaire identique à $G$ mais ayant $T$ pour axiome). -(0) Donner quelques exemples de mots de $L(G)$ et de $L(G,T)$ (au +(0) Donner quelques exemples de mots de $L(S)$ et de $L(T)$ (au moins deux de chaque). -(1) Expliquer brièvement pourquoi $L(G)$ est l'ensemble des mots de la -forme $u_1\cdots u_k$ avec $u_i \in L(G,T)$, et pourquoi $L(G,T)$ est -l'ensemble des mots de la forme $awbw'c$ avec $w,w'\in L(G)$. (Par -conséquent, $L(G,T)$ est l'ensemble des mots de la forme $a u_1 \cdots +(1) Expliquer brièvement pourquoi $L(S)$ est l'ensemble des mots de la +forme $u_1\cdots u_k$ avec $u_i \in L(T)$, et pourquoi $L(T)$ est +l'ensemble des mots de la forme $awbw'c$ avec $w,w'\in L(S)$. (Par +conséquent, $L(T)$ est l'ensemble des mots de la forme $a u_1 \cdots u_k b u'_1\cdots u'_{\ell} c$ avec -$u_1,\ldots,u_k,u'_1,\ldots,u'_{\ell} \in L(G,T)$.) +$u_1,\ldots,u_k,u'_1,\ldots,u'_{\ell} \in L(T)$.) -(2) Comment exprimer $L(G)$ à partir de $L(G,T)$ au moyen d'une ou +(2) Comment exprimer $L(S)$ à partir de $L(T)$ au moyen d'une ou plusieurs opérations rationnelles\footnote{C'est-à-dire : union, concaténation, étoile de Kleene.} ? Y a-t-il inclusion de l'un dans l'autre ? -(3) Montrer que tout mot $w$ appartenant à $L(G)$ ou à $L(G,T)$ a le +(3) Montrer que tout mot $w$ appartenant à $L(S)$ ou à $L(T)$ a le même nombre de $a$, de $b$ et de $c$, c'est-à-dire $|w|_a = |w|_b = |w|_c$ où $|w|_x$ désigne le nombre total d'occurrences de la lettre $x$ dans le mot $w$. (4) Montrer par récurrence sur la longueur $|u|$ d'un mot $u\in -L(G,T)$ que si $v$ est un préfixe de $u$ de longueur $0<|v|<|u|$, +L(T)$ que si $v$ est un préfixe de $u$ de longueur $0<|v|<|u|$, alors on a $|v|_c < |v|_a$. Pour cela, on pourra écrire $u$ sous la forme $a u_1 \cdots u_k b u'_1\cdots u'_{\ell} c$ obtenue en (1), considérer un préfixe\footnote{\label{prefix-note}On signale à toutes @@ -599,50 +605,50 @@ considérer un préfixe\footnote{\label{prefix-note}On signale à toutes de $t_i$.} d'une telle expression, et appliquer la question (3) et l'hypothèse de récurrence. -(5) Déduire des questions (3) et (4) que si $u \in L(G,T)$ et si $v$ +(5) Déduire des questions (3) et (4) que si $u \in L(T)$ et si $v$ est un préfixe de $u$ autre que $u$ lui-même, alors $u \not\in -L(G,T)$. En déduire que $u\in L(G,T)$ et $z \in \Sigma^*$, alors $u$ +L(T)$. En déduire que $u\in L(T)$ et $z \in \Sigma^*$, alors $u$ est l'\emph{unique} préfixe du mot $w := uz$ qui appartienne -à $L(G,T)$ (autrement dit, aucun préfixe de $w$ de longueur ${<}|u|$ -ni ${>}|u|$ n'appartient à $L(G,T)$). +à $L(T)$ (autrement dit, aucun préfixe de $w$ de longueur ${<}|u|$ +ni ${>}|u|$ n'appartient à $L(T)$). (6) En déduire que si un mot $w$ s'écrit $w = u_1\cdots u_k$ avec -$u_1,\ldots,u_k \in L(G,T)$ alors cette factorisation est unique. +$u_1,\ldots,u_k \in L(T)$ alors cette factorisation est unique. (Comment peut-on caractériser $u_1$ comme préfixe de $w$ ?) Montrer de même la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots -u'_\ell$ (on pourra noter que $bz\not\in L(G,T)$ quel que +u'_\ell$ (on pourra noter que $bz\not\in L(T)$ quel que soit $z\in\Sigma^*$). (7) En déduire que la grammaire $G$ est inambiguë. \begin{corrige} -(0) Les mots $abc$ et $aabcbc$ et $ababcc$ appartiennent à $L(G,T)$. - Les mots $\varepsilon$ et $abc$ et $abcabc$ appartiennent à $L(G)$. +(0) Les mots $abc$ et $aabcbc$ et $ababcc$ appartiennent à $L(T)$. + Les mots $\varepsilon$ et $abc$ et $abcabc$ appartiennent à $L(S)$. \smallbreak (1) En bref : il s'agit simplement d'une reformulation des règles de la grammaire. En plus détaillé : si on considère un arbre d'analyse - d'un mot $w$ de $L(G)$, soit il est la dérivation triviale du mot + d'un mot $w$ de $L(S)$, soit il est la dérivation triviale du mot vide, soit sa racine a deux fils étiquetés $T$ et $S$, l'un dont - descend un arbre d'analyse d'un mot $u_1$ de $L(G,T)$ et l'autre - dont descend un arbre d'analyse d'un autre mot $w'$ de $L(G)$, avec + descend un arbre d'analyse d'un mot $u_1$ de $L(T)$ et l'autre + dont descend un arbre d'analyse d'un autre mot $w'$ de $L(S)$, avec $w = u_1 w'$ : en répétant cette remarque jusqu'à tomber sur le mot vide, on voit que $w = u_1 u_2 \cdots u_k$ pour des mots $u_i \in - L(G,T)$ ; et réciproquement, tout mot de cette forme a un arbre + L(T)$ ; et réciproquement, tout mot de cette forme a un arbre d'analyse dans $G$ obtenu en mettant ensemble les arbres d'analyse des $u_i$ (en les associant deux par deux par la droite). Le cas - d'un mot $u$ de $L(G,T)$ est plus simple : son arbre d'analyse donne + d'un mot $u$ de $L(T)$ est plus simple : son arbre d'analyse donne directement une écriture sous la forme $awbw'c$ avec $w,w'$ les mots analysés par les arbres qui descendent des deux fils étiquetés $S$ de la racine (étiquetée $T$). \smallbreak -(2) La description faite en (1) signifie notamment que $L(G) = -L(G,T)^*$ où « $*$ » est l'étoile de Kleene. (Si on veut, la règle $S +(2) La description faite en (1) signifie notamment que $L(S) = +L(T)^*$ où « $*$ » est l'étoile de Kleene. (Si on veut, la règle $S \rightarrow TS \,|\, \varepsilon$ peut s'interpréter comme $S -\rightarrow T{*}$.) En particulier, on a $L(G,T) \subseteq L(G)$. +\rightarrow T{*}$.) En particulier, on a $L(T) \subseteq L(S)$. \smallbreak @@ -651,14 +657,14 @@ L(G,T)^*$ où « $*$ » est l'étoile de Kleene. (Si on veut, la règle $S préservée par toute dérivation immédiate pour $G$ puisqu'elle est préservée en remplaçant $S$ par $TS$ ou par le mot vide et en remplaçant $T$ par $aSbSc$. Elle est donc vérifiée pour tout mot de -$L(G)$ (et en particulier, pour tout mot de $L(G,T)$). +$L(S)$ (et en particulier, pour tout mot de $L(T)$). \smallbreak (4) On procède par récurrence sur $|u|$, ce qui permet de supposer la propriété déjà connue pour tout préfixe $v$ d'un mot de longueur strictement plus courte que $u$. Si $v$ est un préfixe d'un mot $u -\in L(G,T)$, qu'on peut écrire sous la forme $u = a u_1 \cdots u_k b +\in L(T)$, qu'on peut écrire sous la forme $u = a u_1 \cdots u_k b u'_1\cdots u'_{\ell} c$, et si $0<|v|<|u|$, on a soit $v = a u_1 \cdots u_{i-1} y$ où $y \neq \varepsilon$ est un préfixe de $u_i$, soit $v = a u_1\cdots u_k b u'_1\cdots u'_{i-1} y$ où $y \neq @@ -674,44 +680,44 @@ récurrence. \smallbreak -(5) Si $u \in L(G,T)$ et si $v$ est un préfixe de $u$ autre que $u$ +(5) Si $u \in L(T)$ et si $v$ est un préfixe de $u$ autre que $u$ lui-même, alors soit $v = \varepsilon$, qui n'appartient pas à -$L(G,T)$ (par exemple par la question (1)), soit $0<|v|<|u|$, auquel -cas la question (4) donne $|v|_c<|v|_a$, ce qui interdit $v\in L(G,T)$ -d'après (3). Dans tous les cas, $v\not\in L(G,T)$. +$L(T)$ (par exemple par la question (1)), soit $0<|v|<|u|$, auquel +cas la question (4) donne $|v|_c<|v|_a$, ce qui interdit $v\in L(T)$ +d'après (3). Dans tous les cas, $v\not\in L(T)$. -Si maintenant $u\in L(G,T)$ et $z\in\Sigma^*$, un préfixe de $w := uz$ +Si maintenant $u\in L(T)$ et $z\in\Sigma^*$, un préfixe de $w := uz$ est soit un préfixe de $u$ soit de la forme $uz'$ avec $z'$ un préfixe non vide de $z$ (cf. la note \ref{prefix-note}). Un préfixe de $w$ de -longueur ${<}|u|$ n'appartient pas à $L(G,T)$ d'après le paragraphe +longueur ${<}|u|$ n'appartient pas à $L(T)$ d'après le paragraphe précédent, et un mot de la forme $uz'$ ne peut pas y appartenir non plus car c'est alors $u$ lui-même qui serait un préfixe strict de $uz' -\in L(G,T)$ appartenant à $L(G,T)$, ce qui contredit de nouveau le +\in L(T)$ appartenant à $L(T)$, ce qui contredit de nouveau le paragraphe précédent. \smallbreak (6) D'après la question précédente, on peut définir $u_1$ comme -l'unique préfixe de $w$ qui appartient à $L(G,T)$ (tout préfixe +l'unique préfixe de $w$ qui appartient à $L(T)$ (tout préfixe strictement plus court ou strictement plus long n'appartient pas à -$L(G,T)$). Une fois que $u_1$ est défini, en appliquant le même +$L(T)$). Une fois que $u_1$ est défini, en appliquant le même raisonnement au suffixe correspondant $u_2\cdots u_k$, on voit que $u_2$ est défini de façon unique. En procédant ainsi (par récurrence sur $k$ si on veut), les $u_i$ sont définis de façon unique. Le même raisonnement vaut pour $u_1\cdots u_k b u'_1\cdots u'_\ell$ : -on a une factorisation en mots de $L(G,T)\cup\{b\}$ et à chaque fois +on a une factorisation en mots de $L(T)\cup\{b\}$ et à chaque fois le premier facteur est défini comme le seul préfixe possible -appartenant à $L(G,T)\cup\{b\}$. (On utilise le fait que $bz\not\in -L(G,T)$, qui découle du (1), pour voir que $bu'_1\cdots bu'_\ell$ n'a -pas de préfixe dans $L(G,T)$.) +appartenant à $L(T)\cup\{b\}$. (On utilise le fait que $bz\not\in +L(T)$, qui découle du (1), pour voir que $bu'_1\cdots bu'_\ell$ n'a +pas de préfixe dans $L(T)$.) \smallbreak (7) En reprenant l'analyse du (1), il s'agit de montrer que la -factorisation $u_1\cdots u_k$ d'un mot de $L(G)$ est unique et que la +factorisation $u_1\cdots u_k$ d'un mot de $L(S)$ est unique et que la factorisation $a u_1\cdots u_k b u'_1\cdots u'_\ell c$ d'un mot -de $L(G,T)$ l'est aussi. La première partie est exactement une +de $L(T)$ l'est aussi. La première partie est exactement une conclusion du (6), et la seconde l'est aussi dès lors qu'on retire le $a$ initial et le $c$ final. \end{corrige} |