summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2019-01-24 15:24:44 (GMT)
committerDavid A. Madore <david+git@madore.org>2019-01-24 15:24:44 (GMT)
commit79b7a10e9ff4e28617a3381fab09e7dec12a0cef (patch)
tree6745e755d49ca1ff0a2374e764953f77dbfc3589
parentd6dcbb677acf5faefe40ce6a13d8859a4926cd19 (diff)
downloadinf105-79b7a10e9ff4e28617a3381fab09e7dec12a0cef.zip
inf105-79b7a10e9ff4e28617a3381fab09e7dec12a0cef.tar.gz
inf105-79b7a10e9ff4e28617a3381fab09e7dec12a0cef.tar.bz2
Add an intermediate question to make exercise easier.
-rw-r--r--controle-20190205.tex45
1 files changed, 25 insertions, 20 deletions
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 ?
%