summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-03-18 16:41:42 +0100
committerDavid A. Madore <david+git@madore.org>2017-03-18 16:41:42 +0100
commit24815b8b7ed737a0fc1f3fc086249bd781b7549a (patch)
treedfd5c63a85b4c1220f1fa13477665e600cf2d118
parent87ded2fe9da0d6d139573d0ebc670c058e4dab6b (diff)
downloadinf105-24815b8b7ed737a0fc1f3fc086249bd781b7549a.tar.gz
inf105-24815b8b7ed737a0fc1f3fc086249bd781b7549a.tar.bz2
inf105-24815b8b7ed737a0fc1f3fc086249bd781b7549a.zip
Take into account Akim's remarks.
-rw-r--r--controle-20170330.tex18
1 files changed, 6 insertions, 12 deletions
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