Fiddle with vertical spacing (i.e., struggle against TeX's page breaking algorithm).

1 files changed, 39 insertions, 7 deletions

diff --git a/exercices3.tex b/exercices3.tex
index 9774b3a..c2f41cb 100644
--- a/exercices3.tex
+++ b/exercices3.tex
@@ -27,6 +27,8 @@
 \refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
 \newcommand\exercice{%
 \refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
+\newcommand\exercicenobreak{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}}
 \renewcommand{\qedsymbol}{\smiley}
 %
 \newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
@@ -92,10 +94,10 @@ Git: \input{vcline.tex}
 %
 %
 
-\bigbreak
+\bigskip
 \centerline{\textbf{Langages rationnels et automates}}
-
-\exercice
+\penalty8000
+\exercicenobreak
 
 Soit $\Sigma = \{a,b\}$.
 
@@ -166,6 +168,8 @@ finalement obtenu.
 Cet automate n'est pas déterministe : un automate comportant des
 ε-transitions est forcément non-déterministe.
 
+\smallbreak
+
 (2) Tous les états autres que $0$ (car il est initial) et $2,6,8,11$
 (car des transitions non spontanées y aboutissent) vont disparaître ;
 les ε-fermetures $C(q)$ de ces états sont les suivantes :
@@ -214,6 +218,8 @@ que $q^\sharp \in C(q)$, on obtient le NFA suivant :
 Les états $0,2,8,11$ sont finaux car ce sont eux qui ont $13$ dans
 leur ε-fermeture.
 
+\smallbreak
+
 (3) L'automate ainsi obtenu est déjà déterministe incomplet ; pour le
 déterminiser-compléter, il n'y a qu'à ajouter un puits $\bot$ avec la
 seule transition qui manque, c'est-à-dire une transition étiquetée par
@@ -221,6 +227,8 @@ $b$ depuis l'état $6$ (et des transitions de $\bot$ vers lui-même
 étiquetées $a$ et $b$).  Nous ne représentons pas l'automate à $6$
 états ainsi fabriqué.
 
+\smallbreak
+
 (4) On part de l'algorithme déterministe complet obtenu à la
 question (3), et on lui applique l'algorithme de minimisation.  On
 sépare d'abord ses états en deux classes, les finaux $\{0,2,8,11\}$ et
@@ -249,6 +257,8 @@ $\{6,\bot\}$.  On vérifie ensuite qu'aucune transition ne sépare des
 \end{center}
 où l'état $F$ représente la classe $0\equiv 2\equiv 8\equiv 11$.
 
+\smallbreak
+
 (5) Il s'agit du langage constitué des mots n'ayant jamais deux $b$
 consécutifs ni de $b$ final,
 c'est-à-dire des mots dans lesquels chaque $b$ est suivi
@@ -359,10 +369,11 @@ a{*}|a{*}b(ab{*}a|ba{*}b){*}ba{*}
 %
 %
 
-\bigbreak
+\penalty-2000\vskip24ptplus600ptminus12pt
 \centerline{\textbf{Langages algébriques et grammaires hors contexte}}
+\penalty8000
 
-\exercice
+\exercicenobreak
 
 On considère la grammaire hors contexte $G$ suivante (d'axiome $S$)
 sur l'alphabet $\Sigma = \{a,b\}$ :
@@ -425,6 +436,8 @@ et si $u,v\in L$, ils ont des arbres d'analyse $\mathscr{U},
 $a,S,S$, ces deux derniers ayant pour descendants des sous-arbres
 donnés par $\mathscr{U}$ et $\mathscr{V}$.
 
+\smallbreak
+
 (2) Montrons par récurrence sur $|w|$ que si $w \in L$ alors on a $wz
 \not\in L$ pour tout $z \in \Sigma^+$.  La récurrence permet de
 supposer la conclusion déjà connue pour tout mot de longueur $<|w|$.
@@ -449,6 +462,8 @@ longueur du même mot $uvz = u'v'$), et on a alors $v' = vz$, mais
 comme $v\in L$, l'hypothèse de récurrence entraîne $v'\not\in L$,
 encore une contradiction.
 
+\smallbreak
+
 (3) Montrons que si $auv = au'v'$ avec $u,v,u',v'\in L$ alors $u=u'$
 et $v=v'$.  On a notamment $uv = u'v'$.  Distinguons trois cas :
 (i) soit $|u'|>|u|$, mais alors $u$ est un préfixe strict de $u'$,
@@ -461,6 +476,8 @@ L$, de nouveau une contradiction ; (iii) soit $|u'|=|u|$, donc $u'=u$
 (puisqu'ils sont préfixes de même longueur du même mot $uv = u'v'$),
 et on a alors $v' = v$, la conclusion annoncéee.
 
+\smallbreak
+
 (4) Soit $w \in L$ : on veut montrer qu'il a un unique arbre d'analyse
 pour $G$.  On procède par récurrence sur $|w|$, ce qui permet de
 supposer la conclusion connue pour tout mot de longueur $<|w|$.  Comme
@@ -476,6 +493,8 @@ $w=auv$) sont uniquement déterminés, et l'hypothèse de récurrence
 permet de conclure que les arbres d'analyse $\mathscr{U}$ et
 $\mathscr{V}$ sont uniquement déterminés, comme on le voulait.
 
+\smallbreak
+
 (5) Donné un mot $w\in\Sigma^*$, la fonction « rechercher préfixe
   dans $L$ » suivante renvoie la longueur du préfixe de $w$
 appartenant à $L$, ou bien « échec » si ce préfixe n'existe pas :
@@ -575,6 +594,8 @@ que $G$.
 \end{center}
 et son symétrique par rapport à l'axe vertical.
 
+\smallbreak
+
 (2) Montrons que $L$ est égal au langage $L_{(ba){*}b}$ dénoté par
 l'expression rationnelle $(ba){*}b$ comme la question (0) le laisse
 entrevoir.  Pour cela, il suffit de voir que l'ensemble des
@@ -593,6 +614,8 @@ produire n'importe quel nombre $n$ de répéritions du motif $aS$ en
 appliquant $n$ fois la règle $S\rightarrow SaS$ à partir de $S$, et on
 peut ensuite librement transformer certains $S$ en $b$.
 
+\smallbreak
+
 (3) La grammaire $G'$ donnée par $S \rightarrow baS\,|\,b$ engendre le
 même langage que $G$ d'après la question précédente ; et il est
 évident que cette grammaire est inambiguë : toutes les dérivations
@@ -606,10 +629,11 @@ sont de la forme $S \Rightarrow baS \Rightarrow babaS \Rightarrow
 %
 %
 
-\bigbreak
+\penalty-2000\vskip24ptplus600ptminus12pt
 \centerline{\textbf{Calculabilité}}
+\penalty8000
 
-\exercice
+\exercicenobreak
 
 (1) Soit $\Sigma$ un alphabet (i.e., un ensemble fini).  L'ensemble $L
 = \{u^k : u\in\Sigma^*, k\geq 2\}$ des mots qui sont une puissance
@@ -639,6 +663,8 @@ de l'arrêt.)
   renvoyer faux.  Le langage proposé est donc décidable (et \textit{a
     fortiori} semi-décidable).
 
+\smallbreak
+
 (2) Donné un $e \in \mathbb{N}$, la fonction $10^{1000+e}$ est
   évidemment calculable.  On peut ensuite lancer l'exécution du
   $e$-ième programme, sur l'entrée $42$, pour au plus ce nombre
@@ -648,6 +674,8 @@ de l'arrêt.)
   vrai, sinon, on renvoie faux : ceci montre que l'ensemble proposé
   est bien décidable (et \textit{a fortiori} semi-décidable).
 
+\smallbreak
+
 (3) L'ensemble $A$ proposé est « presque » le problème de l'arrêt.  La
   différence est que le problème de l'arrêt est l'ensemble des couples
   $(e,n)$ tels que le $e$-ième programme termine sur l'entrée $n$
@@ -740,6 +768,8 @@ intervenir le mot vide, car si $w$ est factorisable en mots de $L$ en
 faisant intervenir le mot vide, quitte à retirer celui-ci, il est
 encore factorisable en mots non vides de $L$.)
 
+\smallbreak
+
 (B) Les algorithmes sont très semblables à ceux de la partie (A) si ce
 n'est qu'il faut tenir compte de la possibilité qu'ils puissent ne pas
 terminer.  On doit donc les lancer « en parallèle » et pas « en
@@ -831,6 +861,8 @@ $p$ pour lequel $T$ réponde vrai : on termine alors en renvoyant la
 valeur $p$ qu'on a trouvée, qui vérifie $p=f(n)$ par définition
 de $T$.
 
+\smallbreak
+
 Reste à montrer que (3) implique (1) : supposons qu'on ait un
 algorithme $T$ qui « semi-décide » $\Gamma_f$ (i.e., donnés $(n,p)$,
 termine en temps fini et répond oui si $p=f(n)$, et ne termine pas