summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-02-02 10:21:02 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-02-05 11:40:09 (GMT)
commitd091df49fe711210d02b1a9ba85c0259e11d10cf (patch)
tree234608bfd9b9865b17e253128c8e363b0c362cd0
parent3bdb816d69bd10766944867297e2ca2fe769f182 (diff)
downloadinf105-d091df49fe711210d02b1a9ba85c0259e11d10cf.zip
inf105-d091df49fe711210d02b1a9ba85c0259e11d10cf.tar.gz
inf105-d091df49fe711210d02b1a9ba85c0259e11d10cf.tar.bz2
Take into account Akim's remarks.
-rw-r--r--controle-20170207.tex166
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}