1 files changed, 64 insertions, 7 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index b72b754..961a916 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -112,9 +112,66 @@ Git: \input{vcline.tex}
 
 \bigbreak
 
-\section{Alphabets, mots et langages ; langages rationnels}
+\setcounter{comcnt}{0}
+
+\thingy \textbf{Présentation et plan :} On se propose de développer
+ici des techniques mathématiques et algorithmiques ayant à la fois un
+intérêt théorique comme théorie des langages formels, et 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}).
+
+Ces notes sont divisées en grandes parties (inégales) de la manière
+suivante :
+\begin{itemize}
+\item l'étude des expressions rationnelles et des automates finis, et
+  des langages qu'ils définissent, dans les sections
+  \ref{section-languages-and-rational-languages} à \ref{section-recognizable-languages},
+  qui sert notamment dans la recherche de texte et de motifs dans une
+  chaîne de caractères ou un document ;
+\item l'étude de certaines grammaires formelles dans la
+  section \ref{section-context-free-grammars}, qui sert notamment à
+  définir et analyser la syntaxe de langages de programmation ;
+\item une introduction à la calculabilité dans la
+  section \ref{section-computability}, qui place des limites
+  théoriques sur ce qu'un algorithme peut faire.
+\end{itemize}
+
+À 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 :
+\begin{itemize}
+\item les langages « rationnels » (définis par des expressions
+  rationnelles, §\ref{subsection-rational-languages}) et
+  « reconnaissables » (définis par des automates finis,
+  §\ref{section-finite-automata}), qui s'avèrent coïncider
+  (\ref{kleenes-theorem}) ;
+\item les langages « algébriques » (définis par des grammaires hors
+  contexte, §\ref{subsection-context-free-grammars}) ;
+\item les langages « décidables » (définis par un algorithme
+  quelconque, \ref{definition-computable-function-or-set}) et
+  « semi-décidables » (définis par un algorithme qui pourrait ne pas
+  terminer).
+\end{itemize}
+La progression logique vient de l'inclusion qui donne une hiérarchie
+entre ces classes : tout langage rationnel/reconnaissable est
+algébrique (\ref{rational-languages-are-algebraic}), tout langage
+algébrique est décidable (\ref{algebraic-languages-are-decidable}), et
+tout langage décidable est semi-décidable
+(\ref{decidable-iff-semidecidable-and-complement}).  On procède donc
+du plus particulier au plus général.
+
+\thingy \textbf{Notations :} On écrit $A:=B$, ou parfois $B=:A$ pour
+dire que $A$ est défini comme égal à $B$ (cela signifie simplement
+$A=B$ mais en insistant sur le fait que c'est la définition du membre
+du côté duquel se situent les deux points).  On note $\mathbb{N}$
+l'ensemble $\{0,1,2,3\ldots\}$ des entiers naturels.
+
+Le symbole \qedsymbol marque la fin d'une démonstration.
 
-\subsection{Introduction, alphabets, mots et longueur}
+\section{Alphabets, mots et langages ; langages rationnels}\label{section-languages-and-rational-languages}
+
+\subsection{Introduction, alphabets, mots et longueur}\label{subsection-introduction-and-words}
 
 \thingy L'objet de ces notes, au confluent des mathématiques et de
 l'informatique, est l'étude des \textbf{langages} : un langage étant
@@ -432,7 +489,7 @@ des nombres d'occurrences dedans des différentes lettres de
 l'alphabet).\par}
 
 
-\subsection{Langages et opérations sur les langages}
+\subsection{Langages et opérations sur les langages}\label{subjection-languages}
 
 \thingy Un \defin{langage} $L$ sur l'alphabet $\Sigma$ est simplement
 un ensemble de mots sur $\Sigma$.  Autrement dit, il s'agit d'un
@@ -4140,7 +4197,7 @@ tiendrons à l'approche mathématique où on continue à avoir affaire à
 des lettres d'un alphabet $\Sigma$ abstrait.
 
 
-\subsection{Définition, notations et premier exemple}
+\subsection{Définition, notations et premier exemple}\label{subsection-context-free-grammars}
 
 \thingy\label{definition-context-free-grammar} Une \defin{grammaire
   hors contexte} (on dit parfois aussi « sans contexte » ; en anglais,
@@ -5133,7 +5190,7 @@ les automates à pile déterministes (qu'il faut définir soigneusement)
 acceptent strictement moins de langages que les automates à pile
 non déterministes.
 
-\thingy Une approche possible pour résoudre algorithmiquement,
+\thingy\label{algebraic-languages-are-decidable} Une approche possible pour résoudre algorithmiquement,
 \emph{en théorie}, le problème de décider si un mot $w$ appartient au
 langage $L(G)$ engendré par une grammaire $G$ est la suivante :
 \begin{itemize}
@@ -5426,7 +5483,7 @@ bien compte que ces notions étaient forcément toujours incomplètes.)
 
 \bigbreak
 
-\begin{defn}
+\begin{defn}\label{definition-computable-function-or-set}
 On dit qu'une fonction $f\colon\mathbb{N}\to\mathbb{N}$ est
 \defin{calculable (fonction)} (ou \index{récursive
   (fonction)|see{calculable}}« récursive ») lorsqu'il existe un
@@ -5523,7 +5580,7 @@ Les deux propositions suivantes, outre leur intérêt intrinsèque,
 servent à donner des exemples du genre de manipulation qu'on peut
 faire avec la notion de calculabilité et d'algorithme :
 
-\begin{prop}
+\begin{prop}\label{decidable-iff-semidecidable-and-complement}
 Un ensemble $A \subseteq \mathbb{N}$ est décidable ssi $A$ et
 $\mathbb{N}\setminus A$ sont tous les deux semi-décidables.
 \end{prop}