From c0b1c33c01648e7252d1cd78689aa8113369e9cd Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Fri, 1 Feb 2019 01:11:38 +0100
Subject: Take into account Olivier's remarks on exam.

---
 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 6574119..c975ab4 100644
--- a/controle-20190205.tex
+++ b/controle-20190205.tex
@@ -161,7 +161,7 @@ l'automate ainsi obtenu.
 
 (Dans les deux cas, on obtient le même automate $\mathscr{A}_1$, ayant
 $5$ états.  La suite de l'exercice dépendant de cette question, on
-conseille vérifier très soigneusement que $\mathscr{A}_1$ est correct.
+conseille de vérifier très soigneusement que $\mathscr{A}_1$ est correct.
 À défaut de donner l'automate de Glushkov ou de Thompson, donner un
 NFA reconnaissant $L$ pourra apporter une partie des points.)
 
@@ -222,9 +222,9 @@ qu'on a tracé au-dessus (les seuls états qui subsistent après
 quatre états auxquels aboutissent une transition non spontanée).
 \end{corrige}
 
-(2) Déterminiser l'automate $\mathscr{A}_1$ obtenu en (1).  On demande
-un automate fini déterministe \emph{complet}.  On appellera
-$\mathscr{A}_2$ l'automate déterministe en question.
+(2) À partir de $\mathscr{A}_1$, construire un automate fini
+déterministe complet reconnaissant $L$.  On appellera $\mathscr{A}_2$
+l'automate en question.
 
 \begin{corrige}
 L'automate $\mathscr{A}_1$ est déterministe incomplet : il s'agit donc
@@ -394,8 +394,8 @@ S &\rightarrow \varepsilon\\
 
 (1) Montrer que cette grammaire $G$ est ambiguë : pour cela, on
 exhibera deux arbres d'analyse différents du mot $abab$.
-\begin{corrige}
 
+\begin{corrige}
 On peut proposer les arbres d'analyse suivants :\\
 % S<S<e.>a.S<e.>b.S<S<e.>a.S<e.>b.S<e.>>>
 \begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
@@ -441,7 +441,7 @@ d'autre part\\
 La grammaire $G$ est donc ambiguë.
 \end{corrige}
 
-\medbreak
+\bigbreak
 
 \emph{Notation :} Si $w \in \Sigma^*$, on notera $|w|_a$ le nombre
 total d'occurrences de la lettre $a$ dans le mot $w$, et de façon
@@ -551,23 +551,24 @@ que $w$, d'après l'hypothèse de récurrence ils vérifient (A) et (B),
 si bien que $w$ vérifie aussi (A) et (B) d'après la question (4).
 \end{corrige}
 
-(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)\footnote{Autrement dit,
-  le plus long préfixe $w'$ de $v$ tel que pour tout préfixe $u'$
-  de $w'$ (y compris $w'$ lui-même) on ait $|u'|_b\leq |u'|_a$.},
-montrer qu'on a $w = aw'bw''$ pour un certain $w'' \in \Sigma^*$ ;
-puis montrer que $w'$ vérifie (B), puis qu'il vérifie (A), et enfin
-que $w''$ vérifie (A) et (B).
+(6) Soit $w$ un mot \emph{non vide} vérifiant (A) et (B).
+(6.1) Montrer qu'on peut écrire $w = av$ pour un certain $v \in
+\Sigma^*$.  (6.2) Si $w'$ est le plus long préfixe de $v$
+vérifiant (B)\footnote{Autrement dit, le plus long préfixe $w'$ de $v$
+  tel que pour tout préfixe $u'$ de $w'$ (y compris $w'$ lui-même) on
+  ait $|u'|_b\leq |u'|_a$.}, montrer qu'on a $w = aw'bw''$ pour un
+certain $w'' \in \Sigma^*$.  (6.3) Montrer que $w'$ vérifie (B).
+(6.4) Montrer que $w'$ vérifie (A).  (6.5) Montrer que $w''$ vérifie
+(A) et (B).
 
 \begin{corrige}
-Comme $w$ est un mot non vide, on peut parler de sa première
+(6.1) Comme $w$ est un mot non vide, on peut parler de sa première
 lettre $x$, qui en est un préfixe (de longueur $1$), et qui doit
 vérifier $|x|_b \leq |x|_a$ d'après (B), ce qui n'est évidemment
 possible que pour $x=a$.  On a donc $w = av$ où $v$ est le suffixe
 correspondant à $a$.
 
-Remarquons que $|v|_b = |w|_b = |w|_a = 1 + |v|_a$ donc $|v|_b >
+(6.2) Remarquons que $|v|_b = |w|_b = |w|_a = 1 + |v|_a$ donc $|v|_b >
 |v|_a$, et en particulier, $v$ \emph{ne} vérifie \emph{pas} (B).  Si
 maintenant $w'$ est le plus long préfixe de $v$ vérifiant (B), la
 remarque qu'on vient de faire montre que $w' \neq v$, donc il y a au
@@ -578,14 +579,14 @@ vérifie $|va|_b = |v|_b \leq |v|_a < |va|_a$) : on peut donc écrire $v
 = w'bw''$ pour un certain $w''\in\Sigma^*$, c'est-à-dire $w =
 aw'bw''$.
 
-Le mot $w'$ vérifie (B) : en effet, si $u'$ est préfixe de $w'$ alors
+(6.3) Le mot $w'$ vérifie (B) : en effet, si $u'$ est préfixe de $w'$ alors
 $au'$ en est un de $w$, et on a $|u'|_b = |au'|_b \leq |au'|_a =
-1+|u'|_a$.  Montrons par l'absurde que $w'$ vérifie (A) : si ce n'est
+1+|u'|_a$.  (6.4) Montrons par l'absurde que $w'$ vérifie (A) : si ce n'est
 pas le cas, comme $|w'|_b \leq |w'|_a$ (par (B), qu'on vient de
 montrer), on a $|w'|_b < |w'|_a$, mais alors $|w'b|_b = |w'|_b + 1
 \leq |w'|_a = |w'b|_a$ donc $w'b$ vérifie encore (B), ce qui contredit
 le fait que $w'$ était \emph{le plus long} préfixe de $v$
-vérifiant (B).  Le mot $w''$ vérifie (A) : en effet, on a $|w|_b =
+vérifiant (B).  (6.5) Le mot $w''$ vérifie (A) : en effet, on a $|w|_b =
 |w|_a$ (puisque $w$ vérifie (A)), c'est-à-dire $|w'|_b + |w''|_b + 1 =
 |w'|_a + |w''|_a + 1$, et comme on vient de voir que $|w'|_b =
 |w'|_a$, on a aussi $|w''|_b = |w''|_a$.  Enfin, le mot $w''$
@@ -640,9 +641,13 @@ On sait (comme application vue en cours du lemme de pompage) que le
 langage $\{a^k b^k : k\in\mathbb{N}\}$ n'est pas rationnel.
 \end{corrige}
 
-(9) Le langage $L$ est-il rationnel ?
+(9) Le langage $L$ est-il rationnel ?  (On ne cherchera pas à
+appliquer le lemme de pompage pour cette question.)
 
 \begin{corrige}
+Rappelons que le langage $N$ est rationnel (puisque dénoté par une
+expression rationnelle).
+
 Si le langage $L$ était rationnel, alors son intersection $L\cap N$
 avec le langage rationnel $N$ serait aussi rationnelle, mais on vient
 de voir que $L\cap N$ n'est pas rationnel ; c'est donc que $L$ n'est
-- 
cgit v1.2.3

