From 24815b8b7ed737a0fc1f3fc086249bd781b7549a Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Sat, 18 Mar 2017 16:41:42 +0100
Subject: Take into account Akim's remarks.

---
 controle-20170330.tex | 18 ++++++------------
 1 file changed, 6 insertions(+), 12 deletions(-)

(limited to 'controle-20170330.tex')

diff --git a/controle-20170330.tex b/controle-20170330.tex
index db38fc7..1764ad1 100644
--- a/controle-20170330.tex
+++ b/controle-20170330.tex
@@ -136,12 +136,8 @@ concaténation).
 
 On demande l'automate \emph{exact} donné par la construction de
 Thompson pour $r$ : aucune variation ne sera autorisée, même si elle
-conduit à un automate équivalent.
-
-Par ailleurs, pour simplifier le travail du correcteur, on demande
-d'étiqueter les états de $A_1$ par les entiers naturels à partir
-de $0$ (soit $0,1,2,3,\ldots$) dans l'ordre correspondant à la lecture
-de l'expression rationnelle de la gauche vers la droite.
+conduit à un automate équivalent.  Pour simplifier le travail du
+correcteur, on numérotera $0$ l'état initial.
 
 (2) Éliminer les transitions spontanées de l'automate $A_1$ obtenu
 en (1), si nécessaire.  (On supprimera les états devenus inutiles.)
@@ -317,9 +313,7 @@ questions suivantes).
 (3) On \emph{admet}\footnote{Cela pourrait être démontré au moyen du
   lemme de pompage pour les langages algébriques, mais ce n'est pas
   demandé.} que le langage $M' := \{b^p a b^q a b^p a b^q : p,q>0\}$
-n'est pas algébrique.  (Autrement dit, $M'$ est l'ensemble des mots de
-la forme $b^p a b^q a b^p a b^q$ où $p$ et $q$ sont deux entiers
-naturels non nuls.)  En \emph{déduire} que le langage $L'$ n'est pas
+n'est pas algébrique.  En \emph{déduire} que le langage $L'$ n'est pas
 algébrique.  Justifier soigneusement.
 
 Pour cette question et les suivantes, on pourra introduire le langage
@@ -361,8 +355,8 @@ engendre le langage $L$ : en effet, les règles $S\rightarrow aSa$ et
 $S\rightarrow bSb$ permettent de placer des $a$ et $b$ symétriquement
 autour de $S$, c'est-à-dire de produire les $wSw^{\mathsf{R}}$ et donc
 $wAw^{\mathsf{R}}$, tandis que les règles $A\rightarrow\varepsilon$ et
-$A\rightarrow aA$ reviennent à $A\rightarrow a{*}$ et permettent de
-transformer $A$ en un nombre quelconque de $a$.
+$A\rightarrow aA$ permettent de transformer $A$ en un nombre
+quelconque de $a$.
 
 \smallbreak
 
@@ -373,7 +367,7 @@ puisqu'un mot $b^p a b^q a b^p a b^q \in M'$ est évidemment dans $N$
 et par ailleurs peut s'écrire $w a w$ où $w := b^p a b^q$.  Mais
 réciproquement, on a $L'\cap N \subseteq M'$ : en effet, si pour
 certains $w \in \Sigma^*$ et $n \in \mathbb{N}$ le mot $w a^n w$ est
-dans $N$, on a forcément $n\leq 1$ car il n'y a jamais plus qu'un $a$
+dans $N$, on a forcément $n\leq 1$ car il n'y a jamais plus d'un $a$
 consécutif dans un mot de $N$, de là on en déduit que le nombre
 $|w|_a$ de $a$ dans $w$ vaut forcément exactement $1$ et que $n=1$
 (seule possibilité pour avoir trois $a$ dans le mot au total), et
-- 
cgit v1.2.3

