Take into account Antoine's remarks, rework the end of the third exercise.

1 files changed, 79 insertions, 58 deletions

diff --git a/controle-20170207.tex b/controle-20170207.tex
index 7d6a2bc..1d42a3e 100644
--- a/controle-20170207.tex
+++ b/controle-20170207.tex
@@ -93,8 +93,8 @@ très visible dans les copies où commence chaque exercice.
 
 \medbreak
 
-Le sujet étant long pour le temps imparti, il ne sera nécessaire de
-traiter toutes les questions pour obtenir la totalité des points.
+Le sujet étant long pour le temps imparti, il ne sera pas nécessaire
+de traiter toutes les questions pour obtenir la totalité des points.
 
 \medbreak
 
@@ -107,7 +107,7 @@ L'usage des calculatrices électroniques est interdit.
 
 Durée : 1h30
 
-L'énoncé comporte 4 pages.
+L'énoncé comporte 4 pages (page de garde incluse)
 
 \pagebreak
 
@@ -155,7 +155,7 @@ $\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, s'il y en a.
+(2) Éliminer les transitions spontanées de l'automate.
 (On supprimera les états devenus inutiles.)
 
 (3) Déterminiser l'automate ainsi obtenu, si nécessaire.  (On demande
@@ -165,12 +165,12 @@ 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.
+(4) Minimiser l'automate ainsi obtenu, 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$.
 
-(6) Décrire brièvement, en français, le langage ce langage
+(6) Décrire brièvement, en français, ce langage
 complémentaire $\overline{L}$.
 
 (7) (Question bonus, plus longue, à ne traiter qu'en dernier.)  Donner
@@ -330,9 +330,10 @@ 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 »).
+non-déterministe ou incomplet (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
 
@@ -422,9 +423,11 @@ l'expression.)
 
 Soit $\Sigma$ un alphabet (fini, non vide) fixé.  Les questions
 suivantes sont indépendantes (mais on remarquera leur parallélisme).
+Ne pas hésiter à décrire les algorithmes de façon succincte et
+informelle.
 
 (1) Expliquer, au moyen des résultats vus en cours, pourquoi il existe
-un algorithme $A_1$ qui, donnée une expression rationnelle $r$
+un algorithme $A_1$ qui, étant donnée une expression rationnelle $r$
 sur $\Sigma$, décide si le langage $L_r$ dénoté par $r$ est différent
 du langage $\Sigma^*$ de tous les mots sur $\Sigma$.  (Autrement dit,
 l'algorithme $A_1$ doit prendre en entrée une expression rationnelle
@@ -432,8 +435,8 @@ $r$, terminer en temps fini, et répondre « vrai » s'il existe un mot
 $w\in\Sigma^*$ tel que $w\not\in L_r$ et « faux » si $L_r = \Sigma^*$.
 On ne demande pas que l'algorithme soit efficace.)
 
-(2) Expliquer pourquoi il existe un algorithme $A_2$ qui, donnée une
-grammaire hors contexte $G$ sur $\Sigma$, « semi-décide » si le
+(2) Expliquer pourquoi il existe un algorithme $A_2$ qui, étant donnée
+une grammaire hors contexte $G$ sur $\Sigma$, « semi-décide » si le
 langage $L_G$ engendré par $G$ est différent du langage $\Sigma^*$ de
 tous les mots.  (« Semi-décider » signifie que l'algorithme $A_2$ doit
 prendre en entrée une grammaire hors contexte $G$, terminer en temps
@@ -551,8 +554,8 @@ l'indécidabilité du problème de l'arrêt.
 
 \exercice
 
-On considère la grammaire hors-contexte $G$ d'axiome $S$ (et de
-nonterminaux $N = \{S, T\}$) sur l'alphabet $\Sigma = \{a,b,c\}$
+On considère la grammaire hors-contexte $G$ d'axiome $S$ et de
+nonterminaux $N = \{S, T\}$ sur l'alphabet $\Sigma = \{a,b,c\}$
 donnée par
 \[
 \begin{aligned}
@@ -561,7 +564,7 @@ T &\rightarrow aSbSc\\
 \end{aligned}
 \]
 On notera $L(G) = L(G,S)$ le langage qu'elle engendre, et $L(G,T)$ le
-langage des mots qui dérivent de $T$ (c'est-à-dire, si on préfère 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).
 
@@ -570,32 +573,45 @@ 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 la forme $awbw'c$ avec $w,w'\in L(G)$.  (Par
+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
 u_k b u'_1\cdots u'_{\ell} c$ avec
 $u_1,\ldots,u_k,u'_1,\ldots,u'_{\ell} \in L(G,T)$.)
 
-(2) Comment décrire $L(G)$ de en fonction de $L(G,T)$ au moyen des
-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$ de $L(G)$ 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 $|u|$ que si $v$ est un préfixe d'un
-mot $u\in L(G,T)$ de longueur $0<|v|<|u|$, alors on a $|v|_c < |v|_a$.
-(On pourra écrire $u$ sous la forme $a u_1 \cdots u_k b u'_1\cdots
-u'_{\ell} c$ obtenue en (1).)
-
-(5) En déduire que si $u \in L(G,T)$ et $z \in \Sigma^+$ (c'est-à-dire
-$z\in\Sigma^*$ et $z\neq\varepsilon$) alors $uz \not\in L(G,T)$.
-Expliquer par ailleurs pourquoi $bz \not\in L(G,T)$.
+(2) Comment exprimer $L(G)$ à partir de $L(G,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
+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|$,
+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
+  fins utiles le fait évident suivant : un préfixe non vide de $t_1
+  \cdots t_n$ où $t_1,\ldots,t_n \in\Sigma^*$ s'écrit sous la forme
+  $t_1\cdots t_{i-1} y$ où $y\neq\varepsilon$ est un préfixe
+  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$
+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$
+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)$).
 
 (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.
-(Comment peut-on définir $u_1$ en fonction de $w$ ?)  Montrer de même
-la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots u'_\ell$.
+(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
+soit $z\in\Sigma^*$).
 
 (7) En déduire que la grammaire $G$ est inambiguë.
 
@@ -610,8 +626,8 @@ la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots u'_\ell$.
   d'un mot $w$ de $L(G)$, 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 arbre d'analyse d'un autre mot $w'$ de $L(G)$, avec $w
-  = u_1 w'$ : en répétant cette remarque jusqu'à tomber sur le mot
+  dont descend un arbre d'analyse d'un autre mot $w'$ de $L(G)$, 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
   d'analyse dans $G$ obtenu en mettant ensemble les arbres d'analyse
@@ -651,39 +667,44 @@ facteurs $t$ qui interviennent dans cette écriture vérifient $|t|_c
 \leq |t|_a$ : c'est trivial pour $a$ et $b$, c'est le cas pour chaque
 $u_j$ par la question (3), et pour $y$ cela découle soit de
 l'hypothèse de récurrence (lorsque $|y|<|u_i|$ resp. $|y|<|u'_i|$)
-soit par de question (3) (lorsque $y$ est en fait égal à $u_i$
+soit par la question (3) (lorsque $y$ est en fait égal à $u_i$
 resp. $u'_i$).  Comme par ailleurs $|a|_c = 0 < 1 = |a|_a$, une
 égalité est stricte et on en déduit $|v|_c < |v|_a$, ce qui conclut la
 récurrence.
 
-En particulier, on observe pour la question suivante que $v\not\in
-L(G,T)$ pour tout préfixe strict $v$ d'un mot de $L(G,T)$ (si $v =
-\varepsilon$ c'est clair, et si $0<|v|<|u|$, on vient de montrer
-$|v|_c < |v|_a$ alors qu'un mot de $L(G,T)$ vérifie $|u|_c = |u|_a$
-d'après (3)).
-
 \smallbreak
 
-(5) Comme $u$ est un préfixe strict de $uz$, si on avait $uz \in
-L(G,T)$ alors la question (4) implique $u\not\in L(G,T)$, une
-contradiction : c'est donc que $uz \not\in L(G,T)$.
-
-Le fait que $bz \not\in L(G,T)$ est trivial car tout mot de $L(G,T)$
-commence par $a$ d'après la question (1).
+(5) Si $u \in L(G,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)$.
+
+Si maintenant $u\in L(G,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
+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
+paragraphe précédent.
 
 \smallbreak
 
-(6) On peut définir $u_1$ comme l'unique préfixe de $w$ qui appartient
-à $L(G,T)$ (tout préfixe strictement plus court ou strictement plus
-long n'appartient pas à $L(G,T)$ d'après les questions (4) et (5)).
-Une fois que $u_1$ est défini par $w$, en appliquant le même
-raisonnement à $u_2\cdots u_k$ et ainsi de suite, on voit que $u_2$ et
-les autres sont uniquement définis.
+(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
+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
+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 on a vu qu'en
-retirant ou en ajoutant des lettres à la fin d'un mot de ce langage on
-obtient un mot qui n'est pas dans $L(G,T)\cup\{b\}$.
+on a une factorisation en mots de $L(G,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)$.)
 
 \smallbreak