Add more white space to make text less dense.

1 files changed, 260 insertions, 34 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 939abe7..21d4d82 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1,6 +1,6 @@
 %% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
 \documentclass[12pt,a4paper]{article}
-\usepackage[a4paper,hmargin=2cm,vmargin=3cm]{geometry}
+\usepackage[a4paper,hmargin=2.5cm,vmargin=3cm]{geometry}
 \usepackage[francais]{babel}
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
@@ -29,7 +29,7 @@
 \theoremstyle{definition}
 \newtheorem{comcnt}{Tout}[subsection]
 \newcommand\thingy{%
-\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
+\refstepcounter{comcnt}\medskip\noindent\textbf{\thecomcnt.} }
 \newtheorem{defn}[comcnt]{Définition}
 \newtheorem{prop}[comcnt]{Proposition}
 \newtheorem{lem}[comcnt]{Lemme}
@@ -88,6 +88,7 @@ Git: \input{vcline.tex}
 
 \pretolerance=8000
 \tolerance=50000
+\linepenalty=5  % Default is supposedly 10
 
 
 %
@@ -121,6 +122,8 @@ une application informatique pratique à l'analyse de textes ou de
 chaînes de caractères (qu'on appellera par la suite « mots »,
 cf. §\ref{subsection-introduction-and-words}).
 
+\smallbreak
+
 Après des définitions générales (sections
 \ref{subsection-introduction-and-words} à \ref{subjection-languages}),
 ces notes sont divisées en grandes parties (inégales) de la manière
@@ -139,6 +142,8 @@ suivante :
   théoriques sur ce qu'un algorithme peut faire.
 \end{itemize}
 
+\smallbreak
+
 À ces parties seront associées la définition de différentes classes de
 « langages » (voir §\ref{subjection-languages} pour la définition de
 ce terme) qu'il s'agit d'étudier :
@@ -209,6 +214,8 @@ de caractères), mais cette structure supplémentaire ne nous
 intéressera pas ici.  Dans tous les cas, il est important pour la
 théorie que l'alphabet soit \emph{fini}.
 
+\smallskip
+
 L'alphabet sera généralement fixé une fois pour toutes dans la
 discussion, et désigné par la lettre $\Sigma$ (sigma majuscule).
 
@@ -228,6 +235,8 @@ caractères : on écrira donc \texttt{\char`\"foobar\char`\"} pour
 parler du mot en question.  Dans ces notes, nous utiliserons peu cette
 convention.)
 
+\medskip
+
 L'ensemble de tous les mots sur un alphabet $\Sigma$ sera
 désigné $\Sigma^*$ (on verra en \ref{kleene-star} ci-dessous cette
 notation comme un cas particulier d'une construction « étoile » plus
@@ -236,6 +245,8 @@ l'ensemble (infini !) dont les éléments sont toutes les suites finies
 binaires (= suites finies de $0$ et de $1$).  Ainsi, écrire « $w \in
 \Sigma^*$ » signifie « $w$ est un mot sur l'alphabet $\Sigma$ ».
 
+\medskip
+
 {\footnotesize\thingy Typographiquement, on essaiera autant que
   possible de désigner des mots par des variables mathématiques telles
   que $u,v,w$, tandis que $x,y,z$ désigneront plutôt des lettres
@@ -369,6 +380,8 @@ fois du mot $w$.  Formellement, on définit par récurrence :
 peut constater que $w^r w^s = w^{r+s}$ quels que soient
 $r,s\in\mathbb{N}$.)  On a bien sûr $|w^r| = r|w|$.
 
+\smallskip
+
 Cette définition sert notamment à désigner de façon concise les mots
 comportant des répétitions d'une même lettre : par exemple, le mot
 $aaaaa$ peut s'écrire tout simplement $a^5$, et le mot $aaabb$ peut
@@ -405,6 +418,8 @@ produire que le préfixe et le suffixe de longueur $k$ soient égaux
 pour d'autres $k$ que $0$ et $|w|$, comme le montre l'exemple qui
 suit.)
 
+\smallskip
+
 À titre d'exemple, le mot $abbcab$ sur l'alphabet $\Sigma=\{a,b,c,d\}$
 a les sept préfixes suivants, rangés par ordre croissant de longueur :
 $\varepsilon$ (le mot vide), $a$, $ab$, $abb$, $abbc$, $abbca$ et
@@ -421,11 +436,15 @@ et si $w = u_0 v u_1$ est leur concaténation, on dira que $v$ est un
 est déterminé simplement par sa longueur, un facteur est déterminé par
 sa longueur et l'emplacement à partir duquel il commence.
 
+\smallskip
+
 À titre d'exemple, les facteurs du mot $abbcab$ sont : $\varepsilon$
 (le mot vide), $a$, $b$, $c$, $ab$, $bb$, $bc$, $ca$, $abb$, $bbc$,
 $bca$, $cab$, $abbc$, $bbca$, $bcab$, $abbca$, $bbcab$ et $abbcab$
 lui-même.
 
+\smallskip
+
 Dans un contexte informatique, ce que nous appelons ici « facteur »
 est souvent appelé « sous-chaîne [de caractères] ».  Il ne faut
 cependant pas confondre ce concept avec celui de sous-mot défini
@@ -439,6 +458,8 @@ certaines lettres du mot $w$, dans le même ordre, mais en en effaçant
 d'autres ; à la différence du concept de facteur, celui de sous-mot
 n'exige pas que les lettres gardées soient consécutives.
 
+\smallskip
+
 À titre d'exemple, le mot $acb$ est un sous-mot du mot $abbcab$
 (obtenu en gardant les lettres soulignées ici :
 $\underline{a}bb\underline{c}a\underline{b}$ ; pour se rattacher à la
@@ -475,6 +496,8 @@ d'exemple, $(ababb)^{\textsf{R}} = bbaba$.  On remarquera que $(w_1
 w_2)^{\textsf{R}} = w_2^{\textsf{R}} w_1^{\textsf{R}}$ si $w_1,w_2$
 sont deux mots quelconques.
 
+\smallskip
+
 Un mot $w$ est dit \defin{palindrome} lorsque $w = w^{\textsf{R}}$.
 Par exemple, $abba$ est un palindrome sur $\{a,b,c,d\}$ (ou bien le
 mot « ressasser » sur l'alphabet du français).
@@ -563,11 +586,15 @@ langage qu'on vient d'associer l'un à l'autre (par exemple, le langage
 des mots commençant par $a$ et la propriété « commencer par $a$ »), un
 langage pourrait être considéré comme une propriété des mots.
 
-{\footnotesize(Ceci n'a rien de spécifique aux langages : une partie
-  d'un ensemble $E$ quelconque peut être identifiée à une propriété
-  que les éléments de $E$ peuvent ou ne pas avoir, à savoir,
+\smallskip
+
+{\footnotesize(Ce qui précède n'a rien de spécifique aux langages :
+  une partie d'un ensemble $E$ quelconque peut être identifiée à une
+  propriété que les éléments de $E$ peuvent ou ne pas avoir, à savoir,
   appartenir à la partie en question.)\par}
 
+\smallskip
+
 On évitera de faire cette identification pour ne pas introduire de
 complication, mais il est utile de la garder à l'esprit : par exemple,
 dans un langage de programmation fonctionnel, un « langage » au sens
@@ -583,6 +610,8 @@ $L_1,L_2 \subseteq \Sigma^*$), on peut former les langages
 sont simplement les opérations ensemblistes usuelles (entre parties
 de $\Sigma^*$).
 
+\smallskip
+
 Les opérations correspondantes sur les propriétés de mots sont
 respectivement le « ou logique » (=disjonction) et le « et logique »
 (=conjonction) : à titre d'exemple, sur $\Sigma = \{a,b\}$ si $L_1$
@@ -600,6 +629,8 @@ simplement l'ensemble des mots sur $\Sigma$ \emph{n'appartenant pas}
 à $L$.  L'opération correspondante sur les propriétés de mots est la
 négation logique.
 
+\smallskip
+
 À titre d'exemple, sur $\Sigma=\{a,b\}$, si $L$ est le langage des
 mots commençant par $a$, alors $\overline{L}$ est le langage des mots
 ne commençant pas par $a$, c'est-à-dire, la réunion de
@@ -620,6 +651,8 @@ L_1 L_2 &:= \{w_1 w_2 : w_1 \in L_1,\, w_2 \in L_2\}\\
 \end{aligned}
 \]
 
+\smallskip
+
 À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, si on a $L_1
 = \{a,bb\}$ et $L_2 = \{bc, cd\}$ alors $L_1 L_2 = \{abc, acd, bbbc,
 bbcd\}$.
@@ -635,10 +668,14 @@ récurrence :
 \item $L^{r+1} = L^r L$.
 \end{itemize}
 
+\smallskip
+
 À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, si on a $L =
 \{a,bb\}$, alors $L^2 = \{aa, abb, bba, bbbb\}$ et $L^3 = \{aaa, aabb,
 abba, abbbb, \penalty-100 bbaa, bbabb, bbbba, bbbbbb\}$.
 
+\medskip
+
 \emph{Attention}, $L^r$ n'est pas le langage $\{w^r : w\in L\}$
 constitué des répétitions $r$ fois ($w^r$) des mots $w$ de $L$ : c'est
 le langage des concaténations de $r$ mots appartenant à $L$ \emph{mais
@@ -661,17 +698,23 @@ L^* &:= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\
 \end{aligned}
 \]
 
+\smallskip
+
 À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, si on a $L =
 \{a,bb\}$, alors on a $L^* = \{\varepsilon, a, bb, \penalty-200 aa,
 abb, bba, bbbb, \penalty-200 aaa, aabb, abba, abbbb, \penalty-100
 bbaa, bbabb, bbbba, bbbbbb, \ldots\}$.
 
+\smallskip
+
 Comme ci-dessus, il faut souligner que les mots $w_1,\ldots,w_r$
 concaténés n'ont pas à être égaux : notamment, $\{a,b\}^*$ est le
 langage constitué de tous les mots sur l'alphabet $\{a,b\}$, pas le
 langage $\{a\}^* \cup \{b\}^*$ constitué des mots obtenus en répétant
 la lettre $a$ ou en répétant la lettre $b$.
 
+\smallskip
+
 On remarquera que la définition de $L^*$ ci-dessus redonne bien,
 lorsqu'on l'applique à l'alphabet $\Sigma$ lui-même (considéré comme
 langage des mots de longueur $1$), l'ensemble $\Sigma^*$ de tous les
@@ -697,7 +740,7 @@ langage sur l'alphabet $\Sigma$, on définit le langage miroir
 $L^{\mathsf{R}}$ comme l'ensemble des mots miroirs des mots de $L$,
 c'est-à-dire $L^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L\}$.
 
-\medbreak
+\bigbreak
 
 \thingy\label{set-of-languages} De même que l'ensemble des mots sur un
 alphabet $\Sigma$ admet une notation, à savoir $\Sigma^*$, on peut
@@ -712,6 +755,8 @@ synonyme de « $L\subseteq \Sigma^*$ » ou de « $L$ est un langage
 sur $\Sigma$ » ; on évitera cependant de le faire, car cette notation
 est plus lourde qu'utile.
 
+\smallskip
+
 {\footnotesize Il sera marginalement question dans ces notes de
   « classes de langages » : une classe de langages est un ensemble de
   langages (c'est-à-dire une partie de $\mathscr{P}(\Sigma^*)$, ou si
@@ -769,6 +814,8 @@ cf. \ref{concatenation-of-languages}), et l'étoile de Kleene
 (représentant une répétition quelconque d'un certain motif,
 cf. \ref{kleene-star}).
 
+\medskip
+
 L'importance des langages rationnels, et des expressions rationnelles
 (=régulières) qui les décrivent, vient :
 \begin{itemize}
@@ -786,6 +833,8 @@ L'importance des langages rationnels, et des expressions rationnelles
   une chaîne de caractères.
 \end{itemize}
 
+\smallskip
+
 Passons maintenant à une définition plus précise.
 
 \bigbreak
@@ -821,6 +870,8 @@ concaténation de deux langages rationnels, et l'étoile de Kleene d'un
 langage rationnel, sont rationnels ; et les langages rationnels sont
 exactement ceux qu'on obtient ainsi à partir des langages de base.
 
+\smallskip
+
 À titre d'exemple, sur l'alphabet $\{a,b,c,d\}$, comme le langage
 $\{c\}$ (constitué du seul mot $c$) est rationnel, son étoile de
 Kleene, c'est-à-dire $\{c\}^* = \{\varepsilon, c, cc, ccc,
@@ -854,6 +905,8 @@ ensembles $\mathscr{C}$ vérifiant tous ces propriétés, est la classe
 $\mathscr{R}$ des langages rationnels (et un langage rationnel est
 simplement un élément de $\mathscr{R}$).
 
+\medskip
+
 \emph{Attention !}, le fait que la classe $\mathscr{R}$ des langages
 rationnels soit stable par concaténation signifie que si $L_1$ et
 $L_2$ sont rationnels alors le langage $L_1 L_2$ (constitué de tous
@@ -876,6 +929,8 @@ langage « dénoté par l'expression rationnelle $dc{*}$ ».  Ceci fournit
 du même coup une nouvelle définition des langages rationnels : ce sont
 les langages dénotés par une expression rationnelle.
 
+\smallskip
+
 Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$)
 est un mot sur l'alphabet $\Sigma \cup \{\bot,
 \underline{\varepsilon}, {(}, {)}, {|}, {*}\}$, où $\bot,
@@ -949,7 +1004,8 @@ $\Sigma = \{a,b,c,d\}$ :
 \item l'expression rationnelle $(bc){*}$ dénote le langage $\{bc\}^* =
   \{\varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ;
 \item l'expression rationnelle $(a|(bc){*})$ dénote le langage $\{a\}
-  \cup \{bc\}^* = \{a, \varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ;
+  \cup \{bc\}^* = \{a,\penalty0 \varepsilon,\penalty1000
+  bc,\penalty1000 bcbc,\penalty1000 bcbcbc, \ldots\}$ ;
 \item l'expression rationnelle $(a|(bc){*})d$ dénote le langage $\{a, d,
   bcd, bcbcd, bcbcbcd, \ldots\}$ ;
 \item l'expression rationnelle $\bot d$ dénote le langage
@@ -1364,6 +1420,8 @@ se trouve l'automate une fois qu'il a consommé le mot $w$, on dira que
 l'automate \emph{acepte} ou \emph{rejette} le mot selon que $q_n \in
 F$ ou que $q_n \not\in F$.
 
+\smallskip
+
 Graphiquement, on peut présenter la procédure de la manière suivante :
 on part de l'état $q_0$ (sommet du graphe représentant l'automate)
 indiqué par la flèche entrante (pointant de nulle part), et pour
@@ -1419,11 +1477,15 @@ $\delta^*(q_0,w) =: q_n \in F$ ; dans le cas contraire, on dira qu'il
 \textbf{langage accepté}, ou \textbf{reconnu}, ou \textbf{défini}, par
 l'automate $A$.
 
+\smallskip
+
 Un langage $L \subseteq \Sigma^*$ qui peut s'écrire sous la forme du
 langage $L(A)$ accepté par un DFA $A$ s'appelle \defin[reconnaissable
   (langage)]{reconnaissable} (sous-entendu : par automate déterministe
 fini).
 
+\smallskip
+
 On dit que deux DFA $A,A'$ sont \defin[équivalents
   (automates)]{équivalents} lorsqu'ils reconnaissent le même langage,
 i.e., $L(A) = L(A')$.
@@ -1474,6 +1536,8 @@ certain mot).  Dans le cas contraire, l'état est dit
 modifier) les états inaccessibles dans un DFA ne change rien au
 langage reconnu (on obtient des automates équivalents).
 
+\smallskip
+
 Par exemple, dans le DFA qui suit, l'état $2$ est inaccessible
 (l'automate est donc équivalent à celui représenté
 en \ref{discussion-example1}).  On remarquera qu'il ne change rien que
@@ -1538,6 +1602,8 @@ en \ref{definition-dfa} est que la fonction $\delta$ est partielle, ce
 qui signifie qu'elle n'est pas obligatoirement définie sur tout couple
 $(q,x) \in Q\times\Sigma$.
 
+\smallskip
+
 Un DFA est considéré comme un DFAi particulier où la fonction de
 transition $\delta$ se trouve être définie partout.
 
@@ -1546,6 +1612,8 @@ différence près que pour chaque $q\in Q$ et chaque $x\in \Sigma$, il y
 a maintenant \emph{au plus une} (et non plus exactement une) arête
 partant de $q$ et étiquetée par $x$.
 
+\smallskip
+
 L'intérêt informatique des DFAi est de ne pas s'obliger à stocker
 inutilement des transitions et des états inutiles au sens où ils ne
 permettront jamais d'accepter le mot (voir la notion d'automate
@@ -1564,6 +1632,8 @@ fonctionner : l'automate n'a plus d'état, n'effectue plus de
 transition, et n'acceptera pas le mot quelles que soient les lettres
 ultérieures.
 
+\smallskip
+
 Cela revient une fois de plus à dire que le mot $w$ est accepté
 lorsqu'il existe un chemin orienté dans l'automate, reliant l'état
 $q_0$ initial à un état $q_n$ final, et tel que le mot $w = x_1 \cdots
@@ -1595,6 +1665,8 @@ Enfin, l'automate $A$ accepte un mot $w$ lorsque $\delta^*(q_0,w)$
 soit parce que $\delta^*(q_0,w)$ n'est pas défini ou parce qu'étant
 défini il n'appartient pas à $F$), l'automate rejette le mot.
 
+\smallskip
+
 Le langage accepté $L(A)$ et l'équivalence de deux automates sont
 définis de façon analogue aux DFA
 (cf. \ref{definition-recognizable-language}).
@@ -1707,6 +1779,8 @@ DFAi représenté en \ref{discussion-example2b} :
 accessible d'un DFAi comme pour un DFA
 (cf. \ref{definition-dfa-accessible-state}).
 
+\smallskip
+
 On dira en outre d'un état $q$ d'un DFAi qu'il est
 \defin[co-accessible (état)]{co-accessible} lorsqu'il existe un mot $w
 \in \Sigma^*$ tel que $\delta(q,w)$ soit défini et soit final,
@@ -1720,6 +1794,8 @@ DFAi elle présente l'intérêt qu'on peut supprimer les états
 non co-accessibles dans un DFAi (ainsi, bien sûr, que toutes les
 transitions qui y conduisent).
 
+\smallskip
+
 Un DFAi dont tous les états sont à la fois accessibles et
 co-accessibles (on les dit aussi \defin[utile (état)]{utiles}) est
 parfois appelé \defin[émondé (automate)]{émondé}.  On peut émonder un
@@ -1818,6 +1894,8 @@ lorsqu'\emph{il existe} $q_0,\ldots,q_n \in Q$ tels que $q_0 \in I$ et
 $q_n\in F$ et $(q_{i-1},x_i,q_i) \in \delta$ pour chaque $1\leq i\leq
 n$.
 
+\smallskip
+
 La différence cruciale avec les DFAi est donc que, maintenant, il
 pourrait exister plusieurs chemins possibles partant d'un état initial
 dont les transitions sont étiquetées par les lettres du même mot.
@@ -1835,6 +1913,8 @@ un chemin orienté conduisant de $q$ à $q'$ et tel que le mot $w$ soit
 obtenu en lisant dans l'ordre les étiquettes des différentes arêtes de
 ce chemin.
 
+\smallskip
+
 Formellement : si $A = (Q,I,F,\delta)$ est un NFA sur
 l'alphabet $\Sigma$, on définit une relation $\delta^* \subseteq Q
 \times \Sigma^* \times Q$ par $(q,w,q') \in \delta^*$ lorsque $w =
@@ -1850,9 +1930,12 @@ de $w$) :
 \end{itemize}
 
 Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$
-et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$.  Le
-langage accepté $L(A)$ et l'équivalence de deux automates sont définis
-de façon analogue aux DFA
+et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$.
+
+\smallskip
+
+Le langage accepté $L(A)$ et l'équivalence de deux automates sont
+définis de façon analogue aux DFA
 (cf. \ref{definition-recognizable-language}).
 
 \thingy\label{discussion-example4} Pour illustrer le fonctionnement
@@ -1889,7 +1972,7 @@ l'état $0$ et qu'on lui fait consommer un $a$, si ce $a$ sera
 l'avant-dernière lettre, et, dans ce cas, passe dans l'état $1$ pour
 pouvoir accepter le mot.
 
-\medbreak
+\bigbreak
 
 Comme les DFAi avant eux, les NFA sont en fait équivalents aux DFA ;
 mais cette fois-ci, le coût algorithmique de la transformation peut
@@ -1942,6 +2025,8 @@ se voir à travers sa fonction indicatrice, qui est une fonction $Q \to
 procédure décrite dans la démonstration de cette proposition en ne
 gardant que les états accessibles.
 
+\smallskip
+
 Algorithmiquement, la déterminisation de $A$ s'obtient par la
 procéduire suivante :
 \begin{itemize}
@@ -2065,17 +2150,22 @@ est la donnée
 \item d'une relation de transition $\delta \subseteq Q \times
   (\Sigma\cup\{\varepsilon\}) \times Q$.
 \end{itemize}
+
 Autrement dit, on autorise maintenant des transitions étiquetées par
 le mot vide $\varepsilon$ plutôt que par une lettre $x \in\Sigma$ :
 ces transitions sont dites \defin[spontanée (transition)]{spontanées},
 ou
 \index{epsilon-transition@$\varepsilon$-transition|see{spontanée}}\textbf{ε-transitions}.
 
+\smallskip
+
 Soulignons qu'on ne définit les ε-transitions \emph{que} pour les
 automates non-déterministes : ou, pour dire les choses autrement,
 \emph{un automate qui possède des ε-transitions est par nature même
   non-déterministe}.
 
+\smallskip
+
 La représentation graphique des εNFA est évidente (on utilisera le
 symbole « $\varepsilon$ » pour étiqueter les transitions spontanées).
 Un NFA est considéré comme un εNFA particulier pour lequel il n'y a
@@ -2089,6 +2179,8 @@ pourquoi un automate à transition spontanée est forcément
 non-déterministe : ces transitions spontanées ne sont qu'une
 \emph{possibilité}, ce qui sous-entend le non-déterminisme.)
 
+\smallskip
+
 De façon plus précise, un εNFA accepte un mot $w$ lorsqu'\emph{il
   existe} un chemin orienté conduisant d'un état initial $q_0$ à un
 état final $q_n$ et tel que $w$ coïncide avec le mot obtenu en lisant
@@ -2117,9 +2209,12 @@ $(q_{i-1},t_i,q_i) \in\delta$ pour chaque $1\leq i\leq n$, et enfin $w
 = t_1\cdots t_n$.
 
 Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$
-et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$.  Le
-langage accepté $L(A)$ et l'équivalence de deux automates sont définis
-de façon analogue aux DFA
+et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$.
+
+\smallskip
+
+Le langage accepté $L(A)$ et l'équivalence de deux automates sont
+définis de façon analogue aux DFA
 (cf. \ref{definition-recognizable-language}).
 
 \thingy\label{discussion-example5} Voici un exemple de εNFA
@@ -2161,6 +2256,8 @@ l'exemple \ref{discussion-example5} ci-dessus, on a $C(0) = \{0,1,2\}$
 et $C(1) = \{1,2\}$ et $C(2) = \{2\}$.  Dans tout NFA sans
 ε-transitions, on a $C(q) = \{q\}$ pour tout état $q$.)
 
+\smallskip
+
 Il est clair qu'on peut calculer algorithmiquement $C(q)$ (par exemple
 par un algorithme de Dijkstra / parcours en largeur, sur le graphe
 orienté dont l'ensemble des sommets est $Q$ et l'ensemble des arêtes
@@ -2322,6 +2419,8 @@ un DFA $A$ tel que $L = L(A)$.  D'après \ref{completion-of-dfai},
 on peut remplacer « DFA » dans cette définition par « DFAi », « NFA »
 ou « εNFA » sans changer la définition.
 
+\smallskip
+
 Nous allons maintenant montrer que les langages reconnaissables sont
 stables par différentes opérations.  Dans cette section, nous traitons
 le cas des opérations booléennes (complémentaire, union, intersection)
@@ -2464,6 +2563,8 @@ en \ref{rational-languages-are-recognizable} que les langages
 rationnels sont reconnaissables (la réciproque faisant l'objet de la
 section \ref{subsection-rnfa-and-kleenes-algorithm}).
 
+\smallskip
+
 Pour établir ces stabilités, on va travailler sur les NFA et utiliser
 la construction parfois appelée « de Glushkov » ou « automate
 standard » ; ceci fournira un « automate de Glushkov » pour chaque
@@ -2529,7 +2630,7 @@ $q_0$ vers chacun des états qui étaient initiaux dans $A$, puis en
 résultat que ce qui vient d'être dit.)
 \end{proof}
 
-\medbreak
+\bigbreak
 
 On a vu en \ref{dfa-union-and-intersection} une preuve, à base de DFA,
 que $L_1 \cup L_2$ est reconnaissable lorsque $L_1$ et $L_2$ le sont.
@@ -2889,6 +2990,8 @@ de base décrits en \ref{trivial-standard-automata} et en appliquant
 les constructions décrites dans les démonstrations de \ref{nfa-union},
 \ref{nfa-concatenation} et \ref{nfa-star}.
 
+\medskip
+
 Plus exactement, on associe à chaque expression rationnelle $r$ (sur
 un alphabet $\Sigma$ fixé) un automate $A_r$ standard, appelé
 \defin[Glushkov (construction d'automate de)]{automate de Glushkov},
@@ -2911,6 +3014,8 @@ définie en \ref{regular-expressions}) :
   de \ref{nfa-star}.
 \end{itemize}
 
+\smallskip
+
 Cette automate de Glushkov $A_r$ possède les propriétés suivantes :
 \begin{itemize}
 \item c'est un NFA reconnaissant le langage $L(r)$ dénoté par
@@ -3071,6 +3176,8 @@ Elle possède pour sa part les propriétés suivantes :
   concaténation implicite).
 \end{itemize}
 
+\smallskip
+
 Dans les dessins qui suivent, on symbolisera de la manière suivante un
 automate de Thompson $A$ quelconque :
 \begin{center}
@@ -3193,11 +3300,13 @@ très simple à appliquer ; mais elle conduit à des automates rapidement
 énormes, comportant un nombre considérable d'états et de transitions
 spontanées « stupides ».
 
+\medskip
+
 À titre d'exemple, voici l'automate de Thompson, déjà gros, de
 l'expression rationnelle $(a|b){*}b$ :
 
 \begin{center}
-\scalebox{0.75}{%
+\scalebox{0.70}{%
 %%% begin example9 %%%
 
 \begin{tikzpicture}[>=latex,line join=bevel,automaton]
@@ -3237,6 +3346,7 @@ dans $(a|b){*}b$.)
 Pour comparaison, voici son automate de Glushkov :
 
 \begin{center}
+\scalebox{0.85}{%
 %%% begin example9b %%%
 
 \begin{tikzpicture}[>=latex,line join=bevel,automaton]
@@ -3265,6 +3375,7 @@ Pour comparaison, voici son automate de Glushkov :
 \end{tikzpicture}
 
 %%% end example9b %%%
+}
 \end{center}
 
 Il a $4$ états puisqu'il y a $3$ lettres dans $(a|b){*}b$.  Ces états
@@ -3314,6 +3425,7 @@ alphabet $\Sigma$ est la donnée
   $(\mathrm{regexp}(\Sigma))$ désigne l'ensemble des expressions
   rationnelles sur $\Sigma$.
 \end{itemize}
+
 Autrement dit, on autorise maintenant des transitions étiquetées par
 des expressions rationnelles quelconques sur $\Sigma$.  Remarquons
 qu'on doit maintenant demander \emph{explicitement} que l'ensemble
@@ -3336,9 +3448,12 @@ transitions ($w = v_1\cdots v_n$), chacun vérifiant l'expression
 rationnelle qui étiquette la transition (soit $v_i \in L(r_i)$).
 
 Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$
-et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$.  Le
-langage accepté $L(A)$ et l'équivalence de deux automates sont définis
-de façon analogue aux DFA
+et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$.
+
+\smallskip
+
+Le langage accepté $L(A)$ et l'équivalence de deux automates sont
+définis de façon analogue aux DFA
 (cf. \ref{definition-recognizable-language}).
 
 \thingy Un εNFA (ou \textit{a fortiori} un NFA, DFAi ou DFA) est
@@ -3347,12 +3462,16 @@ considéré comme un RNFA particulier dont les transitions sont
 rationnelle) soit par le symbole $\underline{\varepsilon}$ (dénotant
 le langage $\{\varepsilon\}$) dans le cas des transitions spontanées.
 
+\smallskip
+
 Une expression rationnelle $r$ peut aussi être considérée comme un
 RNFA particulier comportant un unique état initial, un unique état
 final, et une unique transition de l'un vers l'autre, étiquetée par
 l'expression $r$ elle-même.  Il est évident que ce RNFA reconnaît
 exactement le langage dénoté par $r$.
 
+\smallskip
+
 La représentation graphique des RNFA ne pose pas de problème
 particulier (voir en \ref{example-of-state-elimination} pour
 différents exemples).
@@ -3369,6 +3488,8 @@ S'il n'y a \emph{aucune} transition de $q$ vers $q'$, on peut toujours
 choisir d'en ajouter une $(q,\bot,q')$ (qui ne peut pas être
 empruntée !) si c'est commode.
 
+\medskip
+
 Comme les εNFA, les NFA et les DFAi avant eux, les RNFA peuvent se
 ramener aux automates précédemment définis :
 
@@ -3423,6 +3544,8 @@ chemin dans ce dernier, suivi d'une transition spontanée depuis un
 état final de $A_{r_j}$.
 \end{proof}
 
+\medskip
+
 Mais la surprise des RNFA est qu'ils peuvent aussi se ramener à des
 expressions rationnelles !
 
@@ -3617,7 +3740,7 @@ conduit à l'automate suivant :
 \noindent et finalement à l'expression rationnelle
 $(0|11|10(1|00){*}01){*}$, qui est équivalente à la précédente.
 
-\medbreak
+\bigbreak
 
 \thingy Donnons encore l'exemple du DFAi suivant :
 
@@ -3683,6 +3806,8 @@ reconnaissables coïncident.  (On pourra donc considérer ces termes
 comme synonymes.)
 \end{thm}
 
+\smallskip
+
 Il faut cependant retenir que s'il y a, mathématiquement, équivalence
 entre ces deux classes de langages, cette équivalence \emph{a un coût
   algorithmique}, c'est-à-dire que la conversion d'une expression
@@ -3705,6 +3830,8 @@ d'expressions rationnelles $r_1,r_2$, de fabriquer algorithmiquement
 une expression rationnelle $r''$ (« conjonction » de $r_1$ et $r_2$)
 qui dénote le langage intersection de ceux dénotés par $r_1$ et $r_2$.
 
+\smallskip
+
 Le coût de ces opérations, cependant, est astronomique : doublement
 exponentiel, puisqu'il s'agit de convertir l'expression en NFA, de
 déterminiser le NFA en DFA (à un premier coût exponentiel),
@@ -3864,6 +3991,8 @@ langage $L$ n'est pas rationnel est donc quelque chose comme ceci :
   être).
 \end{itemize}
 
+\smallskip
+
 Donnons maintenant un exemple d'utilisation du lemme :
 
 \begin{prop}\label{example-of-pumping-lemma}
@@ -3909,6 +4038,8 @@ n'avons pas donné de réponse : comment savoir si deux automates
 \emph{donnés} ou deux expressions rationnelles données (ou un de
 chaque) sont équivalents ?
 
+\smallskip
+
 Pour cela, on va introduire un DFA particulier, \emph{canonique},
 associé à un langage rationnel, qu'on pourra calculer
 algorithmiquement, et qui sera véritablement associé au langage,
@@ -4099,8 +4230,9 @@ chaque classe d'équivalence pour $\equiv$.
 \thingy L'algorithme décrit par la proposition \ref{dfa-minimization}
 porte le nom d'algorithme \index{Moore (algorithme
   de)|see{minimisation}}\textbf{de Moore} ou \defin[minimisation
-  (algorithme de)]{de minimisation} ou \textbf{de réduction}.  Voici
-comment on peut le mettre en œuvre de façon plus concrète :
+  (algorithme de)]{de minimisation} ou \textbf{de réduction}.
+
+Voici comment on peut le mettre en œuvre de façon plus concrète :
 \begin{itemize}
 \item s'assurer qu'on a affaire à un DFA \underline{\emph{complet sans
     état inaccessible}} (si nécessaire, déterminiser l'automate s'il
@@ -4126,6 +4258,8 @@ comment on peut le mettre en œuvre de façon plus concrète :
   du représentant).
 \end{itemize}
 
+\smallskip
+
 La dernière étape (construction de l'automate) permet de vérifier
 qu'on a correctement terminé l'étape précédente (raffinement de la
 partition) : si deux états dans la même classe ont une transition
@@ -4201,6 +4335,8 @@ $\{2,3\}$ et $\{4,5\}$, et à l'automate minimal suivant :
 %%% end example7m %%%
 \end{center}
 
+\medskip
+
 Il est intéressant de voir comment des petits changements sur
 l'automate initial modifient la minimisation.  Si on fait pointer la
 transition étiquetée par $c$ de l'état $1$ vers lui-même (au lieu
@@ -4340,6 +4476,8 @@ l'analyse des langues naturelles ; mais c'est plus en informatique
 qu'en linguistique qu'elles ont trouvé leur utilité, à commencer
 surtout par la définition de la syntaxe du langage ALGOL 60.
 
+\smallskip
+
 Cette fois-ci, on ne s'intéressera pas simplement au langage défini
 (par la grammaire hors contexte, dit langage « algébrique »), mais
 aussi à la manière dont ces mots s'obtiennent par la grammaire, et
@@ -4369,6 +4507,8 @@ d'une nouvelle instruction, et enfin un $\mathtt{fi}$ ; pour définir
 un bloc ($\mathit{Block}$), on peut soit ne rien mettre du tout, soit
 mettre une instruction suivi d'un nouveau bloc ».
 
+\smallskip
+
 Notre but va être d'expliquer quel genre de règles de ce genre on peut
 autoriser, comment elles se comportent, quels types de langages elles
 définissent, et comment on peut analyser (essentiellement, retrouver
@@ -4429,6 +4569,8 @@ lorsqu'ils appartiennent à $N$.  Un mot sur $\Sigma\cup N$
 désigner un mot sur $\Sigma$ (autrement dit, un mot est un pseudo-mot
 ne comportant que des symboles terminaux).
 
+\smallskip
+
 Pour redire les choses autrement, les symboles terminaux sont les
 lettres des mots du langage qu'on cherche à définir ; les symboles
 nonterminaux sont des symboles qui servent uniquement à titre
@@ -4437,6 +4579,8 @@ disparaître finalement.  Un « pseudo-mot » est un mot pouvant contenir
 des nonterminaux, tandis qu'un « mot » sans précision du contraire ne
 contient que des terminaux.
 
+\medskip
+
 {\footnotesize Typographiquement, on aura tendance à utiliser des
   lettres minuscules pour désigner les symboles terminaux, et
   majuscules pour désigner les symboles nonterminaux ; et on aura
@@ -4463,6 +4607,8 @@ $T \mathrel{\rightarrow_G} \alpha$, ou simplement $T \rightarrow
 \alpha$ (lorsque $G$ est clair) pour signifier que $(T,\alpha)$ est
 une règle de $G$.
 
+\smallskip
+
 On définit une relation $\Rightarrow$ en posant $\gamma T \gamma'
 \Rightarrow \gamma\alpha\gamma'$ pour toute règle $(T,\alpha)$ et tous
 pseudo-mots $\gamma,\gamma'$ : autrement dit, formellement, on définit
@@ -4494,6 +4640,8 @@ précisera la grammaire appliquée en écrivant $\lambda
 \mathrel{\Rightarrow_G} \xi$ au lieu de simplement
 $\lambda\Rightarrow\xi$.
 
+\smallskip
+
 Une suite de pseudo-mots $(\lambda_0,\ldots,\lambda_n)$ telle que
 \[
 \lambda_0 \Rightarrow \lambda_1 \Rightarrow \cdots \Rightarrow \lambda_n
@@ -4517,6 +4665,8 @@ qu'on peut passer de $\lambda$ à $\xi$ en effectuant une suite
 chaque étape un nonterminal $T$ par la partie droite $\alpha$ d'une
 règle $T \rightarrow \alpha$ de la grammaire $G$.
 
+\smallskip
+
 Il va de soi qu'un pseudo-mot qui ne comporte que des terminaux, i.e.,
 qui est en fait un mot (sur $\Sigma$), ne peut pas être dérivé plus
 loin.  Ceci justifie au moins en partie la terminologie de
@@ -4530,11 +4680,15 @@ de l'axiome $S$ de $G$, autrement dit :
 L(G) = \{w \in \Sigma^* : S \mathrel{\Rightarrow^*} w\}
 \]
 
+\smallskip
+
 Un langage qui peut s'écrire sous la forme $L(G)$ où $G$ est une
 grammaire hors contexte est appelé \index{hors contexte
   (langage)|see{algébrique}}\textbf{langage hors contexte} ou
 \defin[algébrique (langage)]{algébrique}.
 
+\smallskip
+
 Deux grammaires hors contexte $G$ et $G'$ sont dites \defin[faiblement
   équivalentes (grammaires)]{faiblement équivalentes} ou
 \index{langage-équivalentes (grammaires)|see{faiblement
@@ -4575,6 +4729,8 @@ S b^n \Rightarrow a^n b^n
 Le langage $L(G)$ défini par la grammaire est donc $\{a^n b^n :
 n\in\mathbb{N}\}$.
 
+\smallskip
+
 On a vu en \ref{example-of-pumping-lemma} que ce langage n'est pas
 rationnel : il existe donc des langages algébriques qui ne sont pas
 rationnels.  En revanche, pour ce qui est de la réciproque, on verra
@@ -4599,6 +4755,8 @@ langage défini par la grammaire est l'ensemble de tous les mots (sans
 nonterminaux) qui peuvent s'obtenir par application des règles de
 remplacement à partir de l'axiome.
 
+\smallskip
+
 Les grammaires de types 0 et 1, avec celles de type 2 c'est-à-dire
 hors contexte, et celles de type 3 (= régulières) qui seront définies
 en \ref{regular-grammar} ci-dessous, forment une hiérarchie (plus le
@@ -4611,7 +4769,7 @@ classe de langages définie est petite) appelée \defin[Chomsky
 
 \begin{prop}\label{rational-languages-are-algebraic}
 Tout langage rationnel est algébrique.  Mieux, on peut déduire
-algorithmiquement une grammaire hors contexte $G$ d'un εNFA $A$ de
+algo\-ri\-thmi\-quement une grammaire hors contexte $G$ d'un εNFA $A$ de
 façon à avoir $L(G) = L(A)$.
 \end{prop}
 \begin{proof}
@@ -4785,6 +4943,8 @@ en \ref{example-of-pumping-lemma-for-algebraic-languages}.
 En conséquence, il n'est pas non plus vrai en général que le
 complémentaire d'un langage algébrique soit algébrique.
 
+\smallskip
+
 En revanche, le fait suivant, que nous admettons sans démonstration,
 peut s'avérer utile :
 
@@ -5003,6 +5163,8 @@ suivantes :
 \end{itemize}
 \end{itemize}
 
+\smallskip
+
 On dit de plus que l'arbre est \textbf{complet}, ou simplement qu'il
 s'agit d'un arbre d'analyse, lorsqu'il vérifie la propriété
 supplémentaire suivante :
@@ -5166,10 +5328,14 @@ une dérivation dans laquelle le symbole réécrit est toujours \emph{le
 chaque dérivation immédiate la constituant ne comporte que des
 symboles terminaux.
 
+\smallskip
+
 À titre d'exemple, les deux dérivations données
 en \ref{example-of-derivations} sont respectivement une dérivation
 gauche et une dérivation droite.
 
+\smallskip
+
 À chaque arbre d'analyse est associée une et une seule dérivation
 gauche : on l'obtient de façon évidente en réécrivant à chaque étape
 le symbole nonterminal le plus à gauche en suivant la règle indiquée
@@ -5192,6 +5358,8 @@ L(G)$ a un unique arbre d'analyse ; il revient au même de dire que
 tout mot de $L(G)$ a une unique dérivation droite, ou encore que tout
 mot de $L(G)$ a une unique dérivation gauche.
 
+\smallskip
+
 Les grammaires des langages informatiques réels sont évidemment
 (presque ?) toujours inambiguës : on souhaite qu'un programme
 (c'est-à-dire, dans la terminologie mathématique, un mot du langage)
@@ -5314,6 +5482,8 @@ en \ref{trivial-example-ambiguity}).  L'ambiguïté est donc une
 caractéristique de la \emph{grammaire} hors contexte et non du
 \emph{langage} algébrique qu'elle engendre.
 
+\smallskip
+
 Cependant, certains langages algébriques ne sont définis \emph{que}
 par des grammaires hors contexte ambiguës.  De tels langages sont dits
 \defin[intrinsèquement ambigu (langage algébrique)]{intrinsèquement
@@ -5353,6 +5523,8 @@ où :
 \end{itemize}
 \end{prop}
 
+\smallskip
+
 Donnons maintenant un exemple d'utilisation du lemme :
 
 \begin{prop}\label{example-of-pumping-lemma-for-algebraic-languages}
@@ -5382,6 +5554,8 @@ peut s'avérer utile pour montrer qu'un langage n'est pas algébrique,
 en permettant de simplifier le langage auquel on va appliquer le lemme
 de pompage.
 
+\smallskip
+
 À titre d'exemple, montrons que le langage $L$ formé des mots sur
 $\{a,b,c\}$ ayant le même nombre total de $a$, de $b$ et de $c$
 (autrement dit $\{w \in \{a,b,c\}^* : |w|_a = |w|_b = |w|_c\}$ où
@@ -5421,6 +5595,8 @@ au sommet de la pile (jusqu'à une profondeur bornée), et une fois
 cette transition effectuée, décider de rajouter, retirer ou remplacer
 des symboles au sommet de la pile.
 
+\medskip
+
 {\footnotesize
 
 De façon plus formelle, un \index{automate à pile}automate à pile non déterministe est la
@@ -5438,6 +5614,8 @@ mot $w$ lorsqu'il existe une suite de transitions d'un état initial
 avec pile vide vers un état final avec pile vide qui consomme les
 lettres de $w$.
 
+\smallskip
+
 De façon plus précise, l'automate accepte $w$ lorsqu'il existe
 $q_0,\ldots,q_n \in Q$ (les états traversés) et $t_1,\ldots,t_n \in
 (\Sigma\cup\{\varepsilon\})$ (les symboles consommés) et
@@ -5458,6 +5636,8 @@ des langages acceptés.)
 
 \par}
 
+\medskip
+
 On peut montrer qu'il y a équivalence entre grammaires hors contexte
 et automates à pile non déterministes au sens où tout langage engendré
 par une grammaire hors contexte est le langage accepté par un automate
@@ -5488,6 +5668,8 @@ hors contexte $G$ (absolument quelconque) est la suivante :
   s'arrêter dès qu'on dépasse la longueur $|w|$ à atteindre.
 \end{itemize}
 
+\smallskip
+
 Énonçons précisément le résultat en question :
 
 \begin{thm}\label{algebraic-languages-are-decidable}
@@ -5570,6 +5752,8 @@ de reconnaître si $w \in L(G)$, et fournir une autre démonstration du
 théorème \ref{algebraic-languages-are-decidable}, tout en continuant à
 ne faire aucune hypothèse sur la grammaire hors contexte $G$.
 
+\smallskip
+
 Il s'agit de travailler en deux étapes :
 \begin{itemize}
 \item D'abord, trouver algorithmiquement une grammaire $G'$ et un $E
@@ -5585,6 +5769,8 @@ Il s'agit de travailler en deux étapes :
   savoir si $S \mathrel{\Rightarrow^*} w$).
 \end{itemize}
 
+\smallskip
+
 Détaillons un peu plus chacune de ces étapes.
 
 Pour transformer la grammaire $G$ en une grammaire $G'$ sous forme
@@ -5623,6 +5809,8 @@ normale de Chomsky, on effectue les transformations suivantes :
 L'ordre de ces transformations peut être légèrement varié, mais celui
 proposé ci-dessus est sans doute le meilleur.
 
+\smallskip
+
 Une fois la grammaire $G'$ en forme normale de Chomsky connue,
 lorsqu'on a un mot $w$ dont on cherche à tester s'il appartient
 à $L(G')$, on calcule, pour chaque facteur $u$ de $w$ (identifié par
@@ -5651,6 +5839,8 @@ rechercher toutes les dérivations $Y \Rightarrow X_1 X_2
 donné $v_1$ et $X_2$ a donné $v_2$.  Une fois les $\Lambda(u)$ connus,
 tester si $w \in L(G')$ revient à tester si $S \in \Lambda(w)$.
 
+\smallskip
+
 L'algorithme qu'on vient de décrire (pour tester si $w \in L(G')$ une
 fois $G'$ sous forme normale de Chomsky) porte le nom
 d'\defin[Cocke-Younger-Kasami (algorithme de)]{algorithme de
@@ -5680,6 +5870,8 @@ engendre) ; ces contraintes sont assez techniques et difficiles à
 décrire : dans la pratique, elles consistent essentiellement à essayer
 de fabriquer l'analyseur et à constater si l'algorithme échoue.
 
+\smallskip
+
 Il existe deux principales approches pour construire un analyseur pour
 une grammaire hors contexte (sujette à diverses contraintes
 supplémentaires) ; dans les deux cas, on construit une sorte
@@ -5706,12 +5898,16 @@ les deux cas.   De façon très simplifiée :
   feuilles, et qui restent encore à regrouper.
 \end{itemize}
 
+\smallskip
+
 On peut écrire un analyseur LL ou (plus difficilement) LR à la main
 dans un cas simple, mais en général ces analyseurs sont fabriqués par
 des algorithmes systématiques, implémentés dans des programmes tels
 que YACC ou Bison (qui produit des analyseurs LR, même si Bison peut
 dépasser ce cadre) ou JavaCC (qui produit des analyseurs LL).
 
+\smallskip
+
 L'idée générale à retenir est que les analyseurs LR sont strictement
 plus puissants que les analyseurs LL (ils sont capables d'analyser
 strictement plus de grammaires, cf. \ref{example-lr-non-ll-grammar}),
@@ -5735,6 +5931,8 @@ productions $\varepsilon$ ; on peut imaginer, si on veut, qu'il s'agit
 d'une forme extrêmement primitive de XML où $a$ représente une balise
 ouvrante, $b$ une balise fermante, et $c$ une balise vide).
 
+\medskip
+
 L'approche la plus évidente, si on doit écrire une fonction « analyser
 un mot comme dérivant de $S$ dans cette grammaire » consiste à coder
 deux fonctions mutuellement récursives, « chercher un préfixe qui
@@ -5786,6 +5984,8 @@ $S\rightarrow TS$ et $S\rightarrow c$, on va écrire :
 \end{itemize}
 \end{itemize}
 
+\smallskip
+
 Cette approche réussit sur cette grammaire très simple (où on peut
 notamment se convaincre que l'éventuel préfixe dérivant de $S$ ou de
 $T$ est toujours défini de façon unique).  L'analyseur qu'on vient de
@@ -5806,7 +6006,7 @@ C'est ici l'approche « descendante » : l'arbre se construit à partir
 de la racine et la pile sert à retenir les règles qu'on a commencé à
 reconnaître.
 
-\smallbreak
+\medbreak
 
 L'approche « ascendante » de la même grammaire serait plutôt la
 suivante : on parcourt le mot de gauche à droite en gardant de côté
@@ -5867,6 +6067,8 @@ fastidieux que programmer un ordinateur en assembleur, donc s'il
 s'agit d'exhiber un algorithme, c'est probablement une mauvaise idée
 de l'écrire sous forme de machine de Turing).
 
+\smallskip
+
 Néanmoins, il est essentiel de savoir que ces formalisations
 existent : on peut par exemple évoquer le paradigme du
 $\lambda$-calcul de Church (la première formalisation rigoureuse de la
@@ -5888,6 +6090,8 @@ formelles d'algorithmes, qu'on peut rassembler sous le nom commun de
 \defin[calculable (fonction)]{calculabilité au sens de Church-Turing},
 ou « calculabilité » tout court.
 
+\smallskip
+
 Notamment, quasiment tous les langages de programmation
 informatique\footnote{C, C++, Java, Python, JavaScript, Lisp, OCaml,
   Haskell, Prolog, etc.  Certains langages se sont même révélés
@@ -5906,7 +6110,7 @@ entiers de taille arbitraire, de les comparer et de calculer les
 opérations arithmétiques dessus, et d'effectuer des tests et des
 boucles.
 
-\medbreak
+\bigbreak
 
 \thingy Il faut souligner qu'on s'intéresse uniquement à la question
 de savoir ce qu'un algorithme peut ou ne peut pas faire
@@ -5919,6 +6123,8 @@ produits $pq$ avec $2\leq p,q\leq n-1$ et tester si l'un d'eux est
 égal à $n$, peu importe que cet algorithme soit absurdement
 inefficace.
 
+\smallskip
+
 De même, nos algorithmes sont capables de manipuler des entiers
 arbitrairement grands : ceci permet de dire, par exemple, que toute
 chaîne binaire peut être considérée comme un entier, peu importe le
@@ -5963,9 +6169,11 @@ considérer qu'au lieu de mots on a affaire à des entiers naturels.
 Il va de soi que la concaténation de deux mots, la longueur d'un mot,
 le miroir d'un mot, sont tous calculables algorithmiquement.
 
-On peut considérer que, dans cette partie, le terme de
-\index{langage}« langage » désigne non plus une partie de $\Sigma^*$
-mais une partie de $\mathbb{N}$.
+\smallskip
+
+Grâce au codage de Gödel, on peut considérer que, dans cette partie,
+le terme de \index{langage}« langage » désigne non plus une partie de
+$\Sigma^*$ mais une partie de $\mathbb{N}$.
 
 {\footnotesize (Le remplacement des mots par des entiers naturels en
   utilisant un codage comme on vient de le dire est assez standard en
@@ -5976,7 +6184,7 @@ mais une partie de $\mathbb{N}$.
   d'importance ; comme $\mathbb{N}$ est un objet mathématiquement plus
   simple, c'est surtout pour cela qu'il est utilisé à la place.)\par}
 
-\medbreak
+\bigbreak
 
 \thingy\textbf{Terminaison des algorithmes.} Un algorithme qui
 effectue un calcul utile doit certainement terminer en temps fini.
@@ -6015,6 +6223,8 @@ On dit qu'une fonction $f\colon\mathbb{N}\to\mathbb{N}$ est
 algorithme qui prend en entrée $n\in\mathbb{N}$, termine toujours en
 temps fini, et calcule (renvoie) $f(n)$.
 
+\smallskip
+
 On dit qu'un ensemble $A \subseteq \mathbb{N}$ (un « langage »,
 cf. \ref{computability-all-data-are-integers}) est \defin{décidable}
 (ou \index{calculable (langage)|see{décidable}}« calculable » ou
@@ -6026,6 +6236,8 @@ $n\in\mathbb{N}$, termine toujours en temps fini, et renvoie
 « oui » ($1$) si $n\in A$, « non » ($0$) si $n\not\in A$ (on dira que
 l'algorithme « décide » $A$).
 
+\smallskip
+
 On dit qu'une fonction partielle
 $f\colon\mathbb{N}\dasharrow\mathbb{N}$ (c'est-à-dire une fonction
 définie sur une partie de $\mathbb{N}$, appelé ensemble de définition
@@ -6041,10 +6253,12 @@ On utilisera la notation $f(n)\downarrow$ pour signifier le fait que
 la fonction calculable partielle $f$ est définie en $n$, c'est-à-dire,
 que l'algorithme en question termine.
 
+\smallskip
+
 On dit qu'un ensemble $A \subseteq \mathbb{N}$ est
-\defin{semi-décidable} (ou \index{semi-calculable
-  (langage)|see{semi-décidable}}« semi-calculable » ou
-\index{semi-récursif (langage)|see{semi-décidable}}« semi-récursif »)
+\defin{semi-décidable} (ou
+\index{semi-calculable|see{semi-décidable}}« semi-calculable » ou
+\index{semi-récursif|see{semi-décidable}}« semi-récursif »)
 lorsque la fonction partielle $\mathbb{N}\dasharrow\mathbb{N}$ définie
 exactement sur $A$ et y valant $1$, est calculable partielle.
 Autrement dit : lorsqu'il existe un algorithme qui prend en entrée
@@ -6056,6 +6270,8 @@ et renvoie « oui » ($1$) dans ce cas\footnote{En fait, la valeur
 « semi-décide » $A$).
 \end{defn}
 
+\smallskip
+
 On s'est limité ici à des fonctions d'une seule variable (entière),
 mais il n'y a pas de difficulté à étendre ces notions à plusieurs
 variables, et de parler de fonction calculable $\mathbb{N}^k \to
@@ -6221,6 +6437,8 @@ sont pas importants\footnote{Par exemple, ceux qui aiment le langage
   ce programme est valable (remplacer Java par tout autre langage
   préféré).}.
 
+\medskip
+
 Un point crucial dans cette numérotation des algorithmes est
 l'existence d'une \defin[universelle (machine)]{machine universelle},
 c'est-à-dire d'un algorithme $U$ qui prend en entrée un entier $e$
@@ -6229,6 +6447,8 @@ que $T$ sur l'entrée $n$ (i.e., $U$ termine sur les entrées $e$ et $n$
 si et seulement si $T$ termine sur l'entrée $n$, et, dans ce cas,
 renvoie la même valeur).
 
+\smallskip
+
 Informatiquement, ceci représente le fait que les programmes
 informatiques sont eux-mêmes représentables informatiquement : dans un
 langage de programmation Turing-complet, on peut écrire un
@@ -6248,6 +6468,8 @@ qui, donnée une description (formelle !) d'un algorithme et une entrée
 à laquelle l'appliquer, effectue l'exécution de l'algorithme fourni
 sur l'entrée fournie.
 
+\smallskip
+
 On ne peut pas démontrer ce résultat ici faute d'une description
 rigoureuse d'un modèle de calcul précis, mais il n'a rien de
 conceptuellement difficile (même s'il peut être fastidieux à écrire
@@ -6283,12 +6505,14 @@ programmation demande un minimum d'efforts).
   précisément comment le codage standard est fait pour une
   formalisation de la calculabilité).\par}
 
+\smallskip
+
 La machine universelle n'a rien de « magique » : elle se contente de
 suivre les instructions de l'algorithme $T$ qu'on lui fournit, et
 termine si et seulement si $T$ termine.  Peut-on savoir à l'avance si
 $T$ terminera ?  C'est le fameux « problème de l'arrêt ».
 
-\smallbreak
+\medbreak
 
 Intuitivement, le « problème de l'arrêt » est la question
 « l'algorithme suivant termine-t-il sur l'entrée suivante » ?
@@ -6390,6 +6614,8 @@ semi-décidable, son complémentaire ne l'est pas.
   $h(e, n)$ la fonction qui n'est pas définie si $\varphi_e(n)$ l'est
   et qui vaut $42$ si $\varphi_e(n)$ n'est pas définie.\par}
 
+\medbreak
+
 La non-décidabilité du problème de l'arrêt est un résultat
 fondamental, car très souvent les résultats de non-décidabilité soit
 sont démontrés sur un modèle semblable, soit s'y ramènent
@@ -6439,7 +6665,7 @@ construire un algorithme résolvant le problème de l'arrêt.
   i\leq n\}$ domine asymptotiquement n'importe quelle fonction
   calculable mais c'est un peu plus difficile.\par}
 
-\medbreak
+\bigbreak
 
 {\footnotesize\thingy\textbf{Application à la logique :} Sans rentrer
   dans les détails de ce que signifie un « système formel », on peut