Re-read exam.

1 files changed, 75 insertions, 53 deletions

diff --git a/controle-20170207.tex b/controle-20170207.tex
index f9a138f..a3637f6 100644
--- a/controle-20170207.tex
+++ b/controle-20170207.tex
@@ -87,10 +87,15 @@
 
 \noindent\textbf{Consignes.}
 
-Les exercices sont indépendants sauf dans la mesure où le contraire
-est précisé.  Ils pourront être traités dans un ordre quelconque, mais
-on demande de faire apparaître de façon très visible dans les copies
-où commence chaque exercice.
+Les exercices sont totalement indépendants.  Ils pourront être traités
+dans un ordre quelconque, mais on demande de faire apparaître de façon
+très visible dans les copies où commence chaque exercice.
+
+\medbreak
+
+Le sujet étant délibérément trop long pour le temps imparti, il sera
+possible d'obtenir la totalité des points en ne traitant qu'une partie
+des exercices.
 
 \medbreak
 
@@ -146,8 +151,8 @@ rationnelle qui le dénote.  (On pourra préférer traiter la question
 (1b) Pour chacun des mots suivants, dire s'ils sont dans $L$ ou non :
 $\varepsilon$, $a$, $b$, $ab$, $aa$, $aab$, $aabb$, $abab$, $ababa$.
 (Note : il est conseillé de réutiliser ces mots pour vérifier
-rapidement les réponses aux questions suivantes et ainsi détecter des
-erreurs lors des transformations des automates.)
+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.
 (On supprimera les états devenus inutiles.)
@@ -161,8 +166,8 @@ 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$.
+(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
 complémentaire $\overline{L}$.
@@ -292,6 +297,11 @@ de cet automate de la façon suivante :
 \draw[->] (s22) to[loop below] node[auto]{$b$} (s22);
 \end{tikzpicture}
 \end{center}
+Ici, l'état $0\bullet$ signifie que l'automate n'a pas rencontré
+de $a$, l'état $1\bullet$ qu'il en a rencontré exactement un, et
+l'état $2\bullet$ qu'il en a rencontré au moins deux ; les états
+$\bullet0$, $\bullet1$ et $\bullet2$ ont la même signification pour la
+lettre $b$.
 
 \smallbreak
 
@@ -396,7 +406,9 @@ 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.
+qui vérifie cette propriété suivi d'un suffixe quelconque.  (On
+pouvait utiliser directement ce raisonnement pour produire
+l'expression.)
 \end{corrige}
 
 
@@ -407,7 +419,7 @@ qui vérifie cette propriété suivi d'un suffixe quelconque.
 \exercice
 
 Soit $\Sigma$ un alphabet (fini, non vide) fixé.  Les questions
-suivantes sont indépendantes.
+suivantes sont indépendantes (mais on remarquera leur parallélisme).
 
 (1) Expliquer, au moyen des résultats vus en cours, pourquoi il existe
 un algorithme $A_1$ qui, donnée une expression rationnelle $r$
@@ -424,9 +436,10 @@ 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
 fini en répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que
-$w\not\in L_G$, et ne pas terminer — ou éventuellement terminer en
-répondant « faux » — si $L_G = \Sigma^*$.)  Indication : on peut
-tester tous les mots possibles.
+$w\not\in L_G$, et ne pas terminer\footnote{On peut admettre qu'il
+  termine parfois en répondant « faux », mais ce ne sera pas utile.}
+si $L_G = \Sigma^*$.)  Indication : on peut tester tous les mots
+possibles.
 
 (3) Expliquer pourquoi il existe un tel algorithme $A_3$ : on lui
 fournit en entrée un algorithme $T$ qui décide un langage $L_T
@@ -436,12 +449,11 @@ fini quand on lui présente un mot sur $\Sigma$, et répond « vrai » ou
 « vrai »), et l'algorithme $A_3$ doit semi-décider si $L_T$ est
 différent de $\Sigma^*$.  (C'est-à-dire que $A_3$ doit terminer en
 répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que $w\not\in
-L_T$, et ne pas terminer — ou éventuellement terminer en répondant
-« faux » — si $L_T = \Sigma^*$.)  Indication : la même approche permet
-de traiter les questions (2) et (3).
+L_T$, et ne pas terminer si $L_T = \Sigma^*$.)  Indication : la même
+approche permet de traiter les questions (2) et (3).
 
-(4) Expliquer pourquoi il n'existe pas d'algorithme $A_4$ qui, dans
-les mêmes conditions que $A_3$, décide (au lieu de seulement
+(4) Expliquer pourquoi il \emph{n'existe pas} d'algorithme $A_4$ qui,
+dans les mêmes conditions que $A_3$, décide (au lieu de seulement
 semi-décider) si $L_T$ est différent de $\Sigma^*$.  (C'est-à-dire que
 $A_4$ est censé terminer toujours, et répondre « vrai » s'il existe un
 mot $w\in\Sigma^*$ tel que $w\not\in L_T$, et « faux » si $L_T =
@@ -507,10 +519,10 @@ programme $T$ ne considère que la longueur $|w|$ de $w$, et lance
 étapes : si l'exécution termine dans le temps imparti, alors $T$
 rejette le mot $w$, sinon, il l'accepte (dans tous les cas, $T$
 termine et répond « vrai » ou « faux », donc il est une entrée
-légitime à $A_4$).  Cette construction fait que $L_T$ rejette un mot
-précisément lorsque $S$ termine sur $x$ : si au contraire $S$ ne
-termine pas sur $x$, alors $L_T = \Sigma^*$.  L'utilisation de $A_4$
-sur $T$ permet donc de savoir algorithmiquement si $S$ termine
+légitime à $A_4$).  Cette construction fait que $L_T$ rejette au moins
+un mot précisément lorsque $S$ termine sur $x$ : si au contraire $S$
+ne termine pas sur $x$, alors $L_T = \Sigma^*$.  L'utilisation de
+$A_4$ sur $T$ permet donc de savoir algorithmiquement si $S$ termine
 sur $x$, ce qui contredit l'indécidabilité du problème de l'arrêt.
 
 Variante de la même idée : on appelle « trace d'exécution » de $S$ sur
@@ -537,8 +549,9 @@ l'indécidabilité du problème de l'arrêt.
 
 \exercice
 
-On considère la grammaire hors-contexte $G$ d'axiome $S$ sur
-l'alphabet $\Sigma = \{a,b,c\}$ donnée par
+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}
 S &\rightarrow TS \;|\; \varepsilon\\
@@ -550,29 +563,30 @@ 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)$.
+
 (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)$.  (En
-particulier, $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
+l'ensemble des mots 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)$ simplement en fonction de $L(G,T)$ ?  Y
-a-t-il inclusion de l'un dans l'autre ?
+(2) Comment décrire $L(G)$ de manière simple en fonction de $L(G,T)$ ?
+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 strict
-d'un mot $u\in L(G,T)$, alors $|v|_c < |v|_a$.  (« Préfixe strict »
-signifie que $v$ est un préfixe de $u$ et $v\neq u$.  On pourra écrire
-$u$ sous la forme $a u_1 \cdots u_k b u'_1\cdots u'_{\ell} c$ donnée
-en (1).)
+(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)$.
-Montrer aussi que $bz \not\in L(G,T)$.
+Expliquer par ailleurs pourquoi $bz \not\in 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.
@@ -582,6 +596,11 @@ la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots u'_\ell$.
 (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)$.
+
+\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
@@ -596,7 +615,7 @@ la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots u'_\ell$.
   d'un mot $u$ de $L(G,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.
+  de la racine (étiquetée $T$).
 
 \smallbreak
 
@@ -607,11 +626,12 @@ L(G,T)^*$ où « $*$ » est l'étoile de Kleene.  (Si on veut, la règle $S
 
 \smallbreak
 
-(3) La propriété $|\gamma|_a = |\gamma|_b = |\gamma|_c$ est vérifiée
-pour $S$ et elle est 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)$).
+(3) La propriété $|\gamma|_a = |\gamma|_b = |\gamma|_c$ (ici $\gamma
+\in (\Sigma\cup N)^*$) est vérifiée pour $\gamma = S$ et elle est
+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)$).
 
 \smallbreak
 
@@ -619,22 +639,24 @@ tout mot de $L(G)$ (et en particulier, pour tout mot de $L(G,T)$).
 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
-u'_1\cdots u'_{\ell} c$, on a soit $v = a u_1 \cdots u_{i-1} y$ où $y$
-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$ est un préfixe de $u'_i$.  Dans tous les cas, tous
-les 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$ est un préfixe strict de $u_i$
-resp. $u'_i$) soit par de question (3) (lorsque $y$ est en fait égal à
-$u_i$ resp. $u'_i$).  Comme par ailleurs $|a|_c = 0 < 1 = |a|_a$, une
+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
+\varepsilon$ est un préfixe de $u'_i$.  Dans tous les cas, tous les
+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$
+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)$ (car 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)).
+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