Rework and write solution to third exercise.

1 files changed, 109 insertions, 8 deletions

diff --git a/controle-20170207.tex b/controle-20170207.tex
index 7a941e5..f9a138f 100644
--- a/controle-20170207.tex
+++ b/controle-20170207.tex
@@ -550,23 +550,124 @@ 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).
 
-(1) Comment décrire $L(G)$ simplement en fonction de $L(G,T)$ ?  Y
+(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
+$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) Montrer que tout mot $w$ de $L(G)$ a le même nombre de $a$, de $b$
+(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$.
 
-(3) Montrer que si $u'$ est un mot de $L(G,T)$ et $u$ un préfixe
-strict de $u'$ (c'est-à-dire, un préfixe différent de $u'$ lui-même),
-alors $|u|_c < |u|_a$ ; en déduire qu'il n'appartient pas à $L(G,T)$.
-En d'éduire que si $u \in L(G,T)$ et $z \in \Sigma^+$ (c'est-à-dire
+(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).)
+
+(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)$.
 
-(4) En déduire que si un mot $w$ s'écrit $w = u_1\cdots u_k$ avec
+(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$.
+
+(7) En déduire que la grammaire $G$ est inambiguë.
+
+\begin{corrige}
+(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
+  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
+  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
+  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
+  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.
+
+\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
+\rightarrow TS \,|\, \varepsilon$ peut s'interpréter comme $S
+\rightarrow T{*}$.)  En particulier, on a $L(G,T) \subseteq L(G)$.
+
+\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)$).
+
+\smallbreak
 
-(5) En déduire que la grammaire $G$ est inambiguë.
+(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
+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
+é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)).
+
+\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).
+
+\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.
+
+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\}$.
+
+\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 $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
+conclusion du (6), et la seconde l'est aussi dès lors qu'on retire le
+$a$ initial et le $c$ final.
+\end{corrige}