diff options
| -rw-r--r-- | notes-inf105.tex | 71 |
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} |