summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex135
1 files changed, 83 insertions, 52 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 5c75960..ea0ece6 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -151,17 +151,17 @@ sorte de guillemet pour délimiter les chaînes de caractères : on
écrira donc \texttt{\char`\"foobar\char`\"} pour parler du mot en
question. Dans ces notes, nous utiliserons peu cette convention.)
-L'ensemble des mots sur un alphabet $\Sigma$ est généralement
-désigné $\Sigma^*$ (on verra que l'étoile fait partie d'un usage plus
-général qui sera défini ci-dessous). Par exemple, si $\Sigma =
-\{0,1\}$, alors $\Sigma^*$ est l'ensemble (infini !) dont les éléments
-sont toutes les suites finies binaires (=suites finies de $0$ et
-de $1$).
+L'ensemble des 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 générale). Par
+exemple, si $\Sigma = \{0,1\}$, alors $\Sigma^*$ est l'ensemble
+(infini !) dont les éléments sont toutes les suites finies binaires
+(=suites finies de $0$ et de $1$).
\thingy Le nombre $n$ de lettres dans un mot $w \in \Sigma^*$ est
appelé la \textbf{longueur} du mot, et généralement notée $|w|$ ou
bien $\ell(w)$ : autrement dit, si $x_1,\ldots,x_n \in \Sigma$, alors
-la longueur $\ell(x_1\cdots x_n)$ du mot $x_1\cdots x_n$, vaut $n$.
+la longueur $|x_1\cdots x_n|$ du mot $x_1\cdots x_n$, vaut $n$.
Ceci coïncide bien avec la notion usuelle de longueur d'une chaîne de
caractères en informatique. À titre d'exemple, sur l'alphabet
$\Sigma=\{a,b,c,d\}$, la longueur du mot $abbcab$ vaut $6$ (on écrira
@@ -193,7 +193,8 @@ guillemets.)
La notation $\Sigma^+$ est parfois utilisée pour désigner l'ensemble
des mots \emph{non vides} sur l'alphabet $\Sigma$ (par opposition à
$\Sigma^*$ qui désigne l'ensemble de tous les mots, y compris le mot
-vide).
+vide) ; on verra en \ref{kleene-plus} ci-dessous que c'est un cas
+particulier d'une construction plus générale.
\thingy\label{convention-on-words-of-length-one} Les mots d'une seule
lettre sont naturellement en correspondance avec les lettres
@@ -202,8 +203,8 @@ abusivement, une lettre $x\in\Sigma$ et le mot de longueur $1$ formé
de la seule lettre $x$. (En informatique, cette identification entre
\emph{caractères} et \emph{chaînes de caractères de longueur $1$} est
faite par certains langages de programmation, mais pas par tous :
-\textit{caveat programmator}.) Ceci permet d'écrire par exemple
-$\Sigma \subseteq \Sigma^*$ ou bien $|x|=1 \liff x\in\Sigma$.
+\textit{caveat programmator}.) Cette convention permet d'écrire par
+exemple $\Sigma \subseteq \Sigma^*$ ou bien $|x|=1 \liff x\in\Sigma$.
\thingy\label{number-of-words-of-length-n} Si le cardinal de
l'alphabet $\Sigma$ vaut $\#\Sigma = N$, alors, pour chaque $n$, le
@@ -233,7 +234,7 @@ suivants :
\varepsilon = w$ quel que soit le mot $w \in \Sigma^*$ ;
\item la concaténation est « \textbf{associative} », ce qui signifie
par définition : $u(vw) = (uv)w$ quels que soient les mots $u,v,w
- \in \Sigma^*$.
+ \in \Sigma^*$ (on peut donc noter $uvw$ sans parenthèse).
\end{itemize}
On peut traduire de façon savante ces deux propriétés en une phrase :
@@ -264,8 +265,8 @@ signifie exactement ce qui vient d'être dit).
précisément que $\Sigma^*$ est le \textbf{monoïde libre} sur
l'ensemble $\Sigma$. Par exemple, le morphisme « longueur »
$\ell\colon\Sigma^*\to\mathbb{N}$ est le $\ell = \hat\psi$ obtenu en
- appliquant cette propriété à la fonction $\psi(x) = 1$ pour
- tout $x\in\Sigma$.\par}
+ appliquant cette propriété à la fonction (constante) $\psi(x) = 1$
+ pour tout $x\in\Sigma$.\par}
\thingy\label{powers-of-a-word} Lorsque $w \in \Sigma^*$ et $r \in
\mathbb{N}$, on définit un mot $w^r$ comme la concaténation de $r$
@@ -283,7 +284,7 @@ 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
s'écrire $a^3 b^2$. (De même que pour le mot vide, il faut souligner
-que ces exposants ne font pas partie de l'alphabet.)
+que ces exposants \emph{ne font pas partie} de l'alphabet.)
\thingy Lorsque $u,v,w \in \Sigma^*$ vérifient $w = uv$, autrement dit
lorsque le mot $w$ est la concaténation des deux mots $u$ et $v$, on
@@ -340,21 +341,38 @@ est souvent appelé « sous-chaîne [de caractères] ». Il ne faut
cependant pas confondre ce concept avec celui de sous-mot défini
ci-dessous.
-\thingy\label{definition-subword} Si $u_0,\ldots,u_r$ et
-$v_1,\ldots,v_r$ sont des mots sur un même alphabet $\Sigma$, on dira
-que $v := v_1\cdots v_r$ est un \textbf{sous-mot} du mot $w := u_0 v_1
-u_1 v_2 \cdots u_{r-1} v_r u_r$. En plus clair, cela signifie que $v$
-est obtenu en ne gardant que certaines lettres du mot $w$ (celles
-des $v_i$), dans le même ordre, mais en en effaçant d'autres (celles
-des $u_i$) ; à la différence du concept de facteur, celui de sous-mot
+\thingy\label{definition-subword} Si $w = x_1\cdots x_n$ est un mot de
+longueur $n$, on appelle \textbf{sous-mot} de $w$ un mot de la forme
+$x_{i_1} \cdots x_{i_k}$ où $1\leq i_1 < \cdots < i_k \leq n$. En
+plus clair, cela signifie que $v$ est obtenu en ne gardant que
+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.
À 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
-définition ci-dessus, on pourra prendre $u_0 = \varepsilon$ et $v_1 =
-a$ et $u_1 = bb$ et $v_2 = c$ et $u_2 = a$ et $v_3 = b$ et $u_3 =
-\varepsilon$).
+définition ci-dessus, on pourra prendre $(i_1,i_2,i_3) = (1,4,6)$).
+
+{\footnotesize\thingy Les remarques de dénombrement suivantes peuvent
+ aider à mieux comprendre les notations de préfixe, suffixe, facteur
+ et sous-mot : si $w$ est un mot de longueur $n$, alors il a
+\begin{itemize}
+\item exactement $n+1$ préfixes (car un préfixe est déterminé par sa
+ longueur $k$ entre $0$ et $n$),
+\item exactement $n+1$ suffixes (raison analogue),
+\item au plus $\sum_{k=1}^n (n+1-k) + 1 = \frac{1}{2}(n^2+n+2)$
+ facteurs (car un facteur est déterminé par sa longueur $k$ et son
+ point de départ qui peut être choisi parmi $n+1-k$ possibilités, le
+ $+1$ final étant mis pour le facteur vide),
+\item au plus $2^n$ sous-mots (car un sous-mot est déterminé par
+ l'ensemble $\{i_1,\ldots,i_k\}$ des indices de ses lettres).
+\end{itemize}
+Le nombre exact peut être plus petit en cas de coïncidences entre
+certains choix (par exemple, $aaa$ n'a que $4$ facteurs, $\varepsilon,
+a, aa, aaa$ alors que $abc$ en a bien $\frac{1}{2}(3^2+3+2) = 7$) ;
+mais les bornes ci-dessus sont effectivement atteintes pour certains
+mots.\par}
\thingy\label{definition-mirror-word} Si $w = x_1\cdots x_n$, où
$x_1,\ldots,x_n \in \Sigma$, est un mot de longueur $n$ sur un
@@ -374,7 +392,7 @@ Un mot $w$ est dit \textbf{palindrome} lorsque $w = w^{\textsf{R}}$.
\thingy Un \textbf{langage} $L$ sur l'alphabet $\Sigma$ est simplement
un ensemble de mots sur $\Sigma$. Autrement dit, il s'agit d'un
sous-ensemble (=une partie) de l'ensemble $\Sigma^*$ de tous les mots
-sur $\Sigma^*$ : en symboles, $L \subseteq \Sigma^*$. On souligne
+sur $\Sigma$ : en symboles, $L \subseteq \Sigma^*$. On souligne
qu'on ne demande pas que $L$ soit fini (mais il peut l'être).
\thingy À titre d'exemple, l'ensemble $\{d,dc,dcc,dccc,dcccc,\ldots\}
@@ -392,15 +410,16 @@ Voici quelques autres exemples de langages :
sur l'alphabet $\Sigma = \{p,q,r\}$. Comme on l'a vu
en \ref{number-of-words-of-length-n}, cet ensemble a pour cardinal
exactement $3^{42}$.
+\item Le langage constitué des mots de longueur exactement $1$ sur un
+ alphabet $\Sigma$ (=mots de une seule lettre), qu'on peut identifier
+ à $\Sigma$ lui-même (en identifiant un mot de une lettre à la lettre
+ en question, cf. \ref{convention-on-words-of-length-one}).
\item Le langage (fini) constitué du seul mot vide (=mot de longueur
exactement $0$) sur l'alphabet, disons, $\Sigma = \{p,q,r\}$. Ce
langage $\{\varepsilon\}$ a pour cardinal $1$ (ou $3^0$ si on veut).
Il ne faut pas le confondre avec le suivant :
\item Le langage vide, qui ne contient aucun mot (sur un alphabet
quelconque). Ce langage a pour cardinal $0$.
-\item Le langage constitué des mots de une seule lettre sur un alphabet
- $\Sigma$, qu'on peut identifier à $\Sigma$ lui-même (en identifiant
- un mot de une lettre à la lettre en question).
\item Le langage sur l'alphabet $\Sigma=\{a,b\}$ constitué des mots
qui commencent par trois $a$ consécutifs : ou, si on préfère, qui
ont le mot $aaa$ comme préfixe.
@@ -481,7 +500,7 @@ défini comme l'ensemble des mots $w$ qui peuvent s'écrire comme
concaténation d'un mot $w_1$ de $L_1$ et d'un mot $w_2$ de $L_2$, soit
\[
\begin{aligned}
-L_1 L_2 &= \{w_1 w_2 : w_1 \in L_1,\, w_2 \in L_2\}\\
+L_1 L_2 &:= \{w_1 w_2 : w_1 \in L_1,\, w_2 \in L_2\}\\
&= \{w \in \Sigma^* : \exists w_1 \in L_1\, \exists w_2 \in L_2\,(w = w_1 w_2)\}\\
\end{aligned}
\]
@@ -514,13 +533,13 @@ longueur exactement $r$ sur $\{a,b\}$, ce n'est pas l'ensemble à deux
éléments $\{a^r, b^r\}$ constitué des seuls deux mots $a^r = aaa\cdots
a$ et $b^r = bbb\cdots b$.
-\thingy Si $L$ est un langage sur l'alphabet $\Sigma$, on définit
-enfin l'\textbf{étoile de Kleene} $L^*$ de $L$ comme le langage
-constitué des concaténations d'un nombre \emph{quelconque} de mots
-appartenant à $L$, c'est-à-dire
+\thingy\label{kleene-star} Si $L$ est un langage sur
+l'alphabet $\Sigma$, on définit enfin l'\textbf{étoile de Kleene}
+$L^*$ de $L$ comme le langage constitué des concaténations d'un nombre
+\emph{quelconque} de mots appartenant à $L$, c'est-à-dire
\[
\begin{aligned}
-L^* &= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\
+L^* &:= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\
&= \{w_1\cdots w_r : r\in\mathbb{N},\, w_1,\ldots,w_r\in L\}\\
\end{aligned}
\]
@@ -541,7 +560,7 @@ Le mot vide appartient toujours à $L^*$ (quel que soit $L$) puisque
$L^0 = \{\varepsilon\}$ et qu'on peut prendre $r=0$ ci-dessus
(autrement dit, le mot vide est la concaténation de zéro mots de $L$).
-\thingy\label{kleene-plus} On introduit parfois la notation $L^+ =
+\thingy\label{kleene-plus} On introduit parfois la notation $L^+ :=
\bigcup_{r=1}^{+\infty} L^r = \{w_1\cdots w_r : r>0,\penalty-100\,
w_1,\ldots,w_r\in L\}$ pour l'ensemble des mots formés par
concaténation d'un nombre \emph{non nul} de mots de $L$. Lorsque le
@@ -559,6 +578,8 @@ c'est-à-dire $L^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L\}$.
\subsection{Langages rationnels et expressions rationnelles}\label{subsection-rational-languages}
+\textcolor{red}{TODO: Commencer par une explication informelle.}
+
\thingy Soit $\Sigma$ un alphabet. On va considérer les langages
de base triviaux suivants :
\begin{itemize}
@@ -623,7 +644,7 @@ introduit un nouvel objet, les \textbf{expressions rationnelles}
(certains préfèrent le terme d'\textbf{expressions régulières}), qui
sont des expressions servant à désigner un langage rationnel. Par
exemple, plutôt que d'écrire « $\{d\}(\{c\}^*)$ », on parlera du
-langage désigné par l'expression rationnelle $dc{*}$.
+langage « désigné par l'expression rationnelle $dc{*}$ ».
Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$)
est un mot sur l'alphabet $\Sigma \cup \{\bot,
@@ -656,7 +677,7 @@ d'expression rationnelle $r$ et de \textbf{langage dénoté} (ou
et son langage dénoté est $L_{(r){*}} := L^*$.
\end{itemize}
-À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, $c$ est une
+\thingy À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, $c$ est une
expression rationnelle qui dénote le langage $\{c\}$, donc $(c){*}$ en
est une qui dénote le langage $\{c\}^* = \{\varepsilon, c, cc,
ccc,\ldots\}$, et enfin $d(c){*}$ en est une qui dénote le langage $\{d,
@@ -689,9 +710,10 @@ $\Sigma = \{a,b,c,d\}$ :
Un langage rationnel est par construction la même chose qu'un langage
pour lequel il existe une expression rationnelle qui le dénote.
-On dira qu'un mot $w$ \textbf{vérifie} une expression rationnelle $r$
-lorsque ce mot appartient au langage qu'elle dénote (i.e., $w \in
-L_r$). Par exemple, $dccc$ vérifie l'expression rationnelle $d(c){*}$.
+\thingy On dira qu'un mot $w$ \textbf{vérifie} une expression
+rationnelle $r$ lorsque ce mot appartient au langage qu'elle dénote
+(i.e., $w \in L_r$). Par exemple, $dccc$ vérifie l'expression
+rationnelle $d(c){*}$.
\thingy Deux expressions rationnelles $r_1,r_2$ sont dites
\textbf{équivalentes} lorsqu'elles dénotent le même langage. À titre
@@ -730,10 +752,11 @@ que, en informatique, le symbole \texttt{+} est utilisé par de
nombreux moteurs d'expressions régulières (par exemple,
\texttt{egrep}) pour dénoter l'opération évoquée en \ref{kleene-plus},
i.e., « au moins une répétition » alors que l'étoile signifie « un
- nombre quelconque de répétitions » : si on veut, $r{+}$ a le même
-sens que $rr{*}$. Dans le même contexte, le symbole \texttt{?} est
-souvent utilisé pour désigner « au plus une répétition » : si on veut,
-$r{?}$ a le même sens que $(\underline{\varepsilon}|r)$.
+nombre quelconque de répétitions » : si on veut, $r{\scriptstyle +}$ a
+le même sens que $rr{*}$. Dans le même contexte, le symbole
+\texttt{?} est souvent utilisé pour désigner « au plus une
+répétition » : si on veut, $r{?}$ a le même sens
+que $(\underline{\varepsilon}|r)$ (cf. \ref{remarks-egrep-plus-etc}).
\subsection{Remarques sur les moteurs d'expressions régulières en informatique}
@@ -759,15 +782,15 @@ désigne le langage $\{a^nba^n : a\in\mathbb{N}\} = \{b,aba,
aabaa,\ldots\}$ des mots formés d'un nombre quelconque de $a$ puis
d'un $b$ puis de la \emph{même suite de $a$}, et ce langage
\emph{n'est pas rationnel} au sens mathématique (ce sera une
-conséquence du « lemme de pompage »).
+conséquence du « lemme de pompage » \ref{pumping-lemma}).
-\thingy Il existe aussi un certain nombre de constructions qui, sans
+\thingy\label{remarks-egrep-plus-etc} Il existe aussi un certain nombre de constructions qui, sans
dépasser la puissance des expressions rationnelles au sens
mathématique, apportent des commodités d'écriture dans un contexte
informatique. On a déjà mentionné les symboles \texttt{+} (pour « au
- moins une répétition » : $r{+}$ est équivalent à $rr{*}$) et
-\texttt{?} (pour « au plus une répétition » : $r{?}$ est équivalent à
-$(\underline{\varepsilon}|r)$). Parmi d'autres constructions du
+moins une répétition » : $r{\scriptstyle +}$ est équivalent à $rr{*}$)
+et \texttt{?} (pour « au plus une répétition » : $r{?}$ est équivalent
+à $(\underline{\varepsilon}|r)$). Parmi d'autres constructions du
genre, mentionnons encore le point \texttt{.} qui désigne un caractère
quelconque de l'alphabet (on peut le voir comme une abréviation pour
$(x_1|x_2|\ldots|x_N)$ où $x_1,x_2,\ldots,x_N$ sont tous les éléments
@@ -857,6 +880,9 @@ possibles. L'automate prendra une décision (passer dans un nouvel
état) en fonction de son état actuel et de la lettre qu'on lui donne à
consommer.
+\textcolor{red}{TODO: Commencer par une explication informelle et
+ évoquer les différentes sortes d'automates.}
+
\subsection{Automates finis déterministes complets (=DFA)}
\thingy\label{definition-dfa} Un \textbf{automate fini déterministe}
@@ -933,6 +959,9 @@ 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$.
+\textcolor{red}{TODO: Redire en termes de suites d'états comme
+ en \ref{rnfa-multiple-transition-relation}.}
+
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
@@ -965,6 +994,8 @@ Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$
$\delta^*(q_0,w) =: q_n \in F$ ; dans le cas contraire, on dira qu'il
\textbf{rejette} le mot $w$.
+\textcolor{red}{TODO: Explication informelle.}
+
\thingy\label{definition-recognizable-language} L'ensemble $L_A$ des
mots acceptés par l'automate $A$ s'appelle \textbf{langage accepté},
ou \textbf{reconnu}, ou \textbf{défini}, par l'automate $A$.
@@ -982,7 +1013,7 @@ faire la description informelle suivante : l'automate commence dans
l'état $0$, où il reste jusqu'à rencontrer un $a$ qui le fait passer
dans l'état $1$, où il reste ensuite jusqu'à rencontrer un $b$ qui le
fait passer dans l'état $2$, où il reste définitivement et qui
-constitue un état acceptant.
+constitue le seul état acceptant.
\begin{center}
%%% begin example2 %%%
@@ -1452,7 +1483,7 @@ partant de $0$ et étiquetée par $a$, tandis que $\delta'(\{0\},b) =
\{0\}$ ; ensuite, $\delta'(\{0,1\},a) = \{0,1,2\}$ car $0,1,2$ sont
les trois états auxquels on peut arriver dans $A$ par une transition
partant de $0$ ou $1$ et étiquetée par $a$ ; et ainsi de suite. En
-procédant ainsi, on constuit l'automate à $4$ états qui suit :
+procédant ainsi, on construit l'automate à $4$ états qui suit :
\begin{center}
\footnotesize
@@ -2049,7 +2080,7 @@ qu'on doit maintenant demander explicitement que l'ensemble $\delta$
des transitions permises soit fini car l'ensemble $Q \times
(\mathrm{regexp}(\Sigma)) \times Q$, lui, ne l'est pas.
-\thingy Pour un tel automate, on définit une relation $\delta^*
+\thingy\label{rnfa-multiple-transition-relation} Pour un tel automate, on définit une relation $\delta^*
\subseteq Q \times \Sigma^* \times Q$ par $(q,w,q') \in \delta^*$
lorsqu'il existe $q_0,\ldots,q_n \in Q$ et $r_1,\ldots,r_n \in
\mathrm{regexp}(\Sigma)$ tels que $q_0 = q$ et $q_n = q'$ et