From 79b7a10e9ff4e28617a3381fab09e7dec12a0cef Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 24 Jan 2019 16:24:44 +0100
Subject: Add an intermediate question to make exercise easier.

---
 controle-20190205.tex | 45 +++++++++++++++++++++++++--------------------
 1 file changed, 25 insertions(+), 20 deletions(-)

(limited to 'controle-20190205.tex')

diff --git a/controle-20190205.tex b/controle-20190205.tex
index 3802f51..a3e6f08 100644
--- a/controle-20190205.tex
+++ b/controle-20190205.tex
@@ -411,37 +411,42 @@ suivantes :
 inférieur ou égal au nombre de $a$, et pour le mot $w$ tout entier il
 y a égalité).
 
-(2) Expliquer \emph{brièvement} pourquoi, si $w,w',w'' \in \Sigma^*$,
-alors tout préfixe du mot $waw'bw''$ est d'une des trois formes
-suivantes : (i) $u$ pour $u$ un préfixe de $w$, (ii) $wau'$ pour
-$u'$ un préfixe de $w'$, ou (iii) $waw'bu''$ pour $u''$ un préfixe
-de $w''$.  (On rappelle que le mot vide et le mot tout entier comptent
-pour préfixes d'un mot.)
-
-(3) Si $w,w',w'' \in \Sigma^*$ vérifient tous les trois la
-propriété (A) ci-dessus, montrer que c'est encore le cas
-de $waw'bw''$.  Si $w,w',w'' \in \Sigma^*$ vérifient tous les trois la
-propriété (B) ci-dessus, montrer que c'est encore le cas
-de $waw'bw''$ (on utilisera pour cela la question (2)).
-
-(4) Déduire de la question (3) que tout mot de $L$ vérifie (A) et (B).
-(Autrement dit, on vient de montrer : $L \subseteq M$.)
-
-(5) Soit $w$ un mot \emph{non vide} vérifiant (A) et (B) : montrer
+(2) Expliquer pourquoi un mot $w \in \Sigma^*$ appartient à $L$ si et
+seulement si $w = \varepsilon$ \emph{ou bien} $w$ s'écrit sous la
+forme $w_1 a w_2 b w_3$ où $w_1,w_2,w_3$ appartiennent à $L$.  (On
+pourra, par exemple, raisonner sur les arbres d'analyse.)
+
+(3) Expliquer \emph{brièvement} pourquoi, si $w_1, w_2, w_3 \in
+\Sigma^*$, alors tout préfixe du mot $w_1 a w_2 b w_3$ est d'une des
+trois formes suivantes : (i) $u_1$ pour $u_1$ un préfixe de $w_1$,
+(ii) $w_1 a u_2$ pour $u_2$ un préfixe de $w_2$, ou (iii) $w_1 a w_2 b
+u_3$ pour $u_3$ un préfixe de $w_3$.  (On rappelle que le mot vide et
+le mot tout entier comptent pour préfixes d'un mot.)
+
+(4) Si $w_1, w_2, w_3 \in \Sigma^*$ vérifient tous les trois la
+propriété (A) ci-dessus, montrer que c'est encore le cas de $w_1 a w_2
+b w_3$.  Si $w_1, w_2, w_3 \in \Sigma^*$ vérifient tous les trois la
+propriété (B) ci-dessus, montrer que c'est encore le cas de $w_1 a w_2
+b w_3$ (on utilisera pour cela la question (3)).
+
+(5) Déduire des questions (2) et (4) que tout mot de $L$ vérifie
+(A) et (B).  (Autrement dit, on vient de montrer : $L \subseteq M$.)
+
+(6) Soit $w$ un mot \emph{non vide} vérifiant (A) et (B) : montrer
 qu'on peut écrire $w = av$ pour un certain $v \in \Sigma^*$ ; si $w'$
 est le plus long préfixe de $v$ vérifiant (B), montrer que $w =
 aw'bw''$ où $w'$ et $w''$ vérifient tous les deux (A) et (B).
 
-(6) Déduire de la question (5) que tout mot vérifiant (A) et (B)
+(7) Déduire des questions (2) et (6) que tout mot vérifiant (A) et (B)
 appartient à $L$.  (Autrement dit, on vient de montrer : $M \subseteq
 L$.  On a donc $L = M$.)
 
-(7) En notant $N = \{a^i b^j : i,j\in\mathbb{N}\}$ le langage défini
+(8) En notant $N = \{a^i b^j : i,j\in\mathbb{N}\}$ le langage défini
 par l'expression rationnelle $a{*}b{*}$, et en utilisant la
 description qu'on vient de trouver pour $L$ (comme l'ensemble des mots
 vérifiant (A) et (B)), déterminer $L \cap N$.  Est-il rationnel ?
 
-(8) Le langage $L$ est-il rationnel ?
+(9) Le langage $L$ est-il rationnel ?
 
 
 %
-- 
cgit v1.2.3

