From 9bc4d34e3a51d321e8a1f4946e83417fd79ac65a Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Wed, 8 Nov 2017 15:02:53 +0100
Subject: Add more white space to make text less dense.
---
notes-inf105.tex | 294 ++++++++++++++++++++++++++++++++++++++++++++++++-------
1 file 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
--
cgit v1.2.3