summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-inf105.tex130
1 files changed, 97 insertions, 33 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index ea0ece6..8847dd2 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -143,29 +143,41 @@ parle plutôt de \textbf{chaîne de caractères}, qui est une suite finie
(=liste) de caractères. Le mot est désigné en écrivant les lettres
les unes à la suite des autres : autrement dit, si $x_1,\ldots,x_n \in
\Sigma$ sont des lettres, le mot formé par la suite finie
-$x_1,\ldots,x_n$ est simplement écrit $x_1\cdots x_n$. À titre
-d'exemple, $abbcab$ est un mot sur l'alphabet $\Sigma = \{a,b,c,d\}$,
-et \texttt{foobar} est un mot (=chaîne de caractères) sur l'alphabet
-ASCII. (Dans un contexte informatique, il est fréquent d'utiliser une
-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$ 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 $|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
-$|abbcab|=6$ ou bien $\ell(abbcab)=6$).
+$x_1,\ldots,x_n$ est simplement écrit $x_1\cdots x_n$.
+
+À titre d'exemple, $abbcab$ est un mot sur l'alphabet $\Sigma =
+\{a,b,c,d\}$, et \texttt{foobar} est un mot (=chaîne de caractères)
+sur l'alphabet ASCII. (Dans un contexte informatique, il est fréquent
+d'utiliser une 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 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
+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$). Ainsi, écrire « $w \in
+\Sigma^*$ » signifie « $w$ est un mot sur l'alphabet $\Sigma$ ».
+
+{\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
+ quelconques dans un alphabet (quant à $a,b,c$, ils serviront de
+ lettres dans les exemples). Ce n'est malheureusement pas possible
+ d'être systématique (il arrivera que $x$ désigne un mot) : on
+ cherchera donc à toujours rappeler le type de toute variable en
+ écrivant, par exemple, $t \in\Sigma$ ou $t \in\Sigma^*$.\par}
+
+\thingy\label{length-of-word} 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 $|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 $|abbcab|=6$ ou bien $\ell(abbcab)=6$).
\thingy Quel que soit l'alphabet, il existe un unique mot de
longueur $0$, c'est-à-dire un unique mot n'ayant aucune lettre, appelé
@@ -250,7 +262,8 @@ entre le monoïde $\Sigma^*$ des mots (pour la concaténation) et le
monoïde $\mathbb{N}$ des entiers naturels (pour l'addition) (cela
signifie exactement ce qui vient d'être dit).
-{\footnotesize\thingy \textbf{Complément :} Le monoïde $\Sigma^*$
+{\footnotesize\thingy\label{universal-property-remark}
+ \textbf{Complément :} Le monoïde $\Sigma^*$
possède la propriété suivante par rapport à l'ensemble $\Sigma$ : si
$M$ est un monoïde quelconque (c'est-à-dire un ensemble muni d'une
opération binaire associative $\cdot$ et d'un élément $e$ neutre
@@ -386,14 +399,32 @@ w_1^{\textsf{R}}$ si $w_1,w_2$ sont deux mots quelconques.
Un mot $w$ est dit \textbf{palindrome} lorsque $w = w^{\textsf{R}}$.
+{\footnotesize\thingy\label{number-of-occurrences-of-letter} La
+ notation suivante est souvent utile : si $w$ est un mot sur un
+ alphabet $\Sigma$ et si $z$ est une lettre (= élément de $\Sigma$),
+ on note $|w|_z$ le nombre total d'occurrences de la lettre $z$
+ dans $w$. À titre d'exemple, sur l'alphabet $\Sigma=\{a,b,c,d\}$,
+ le nombre d'occurrences des différentes lettres dans le mot $abbcab$
+ sont : $|abbcab|_a=2$, $|abbcab|_b=3$, $|abbcab|_c=1$ et
+ $|abbcab|_d=0$.
+
+Formellement, on peut définir $|w|_z$ de la façon suivante : si $w =
+x_1 \cdots x_n$ où $x_1,\ldots,x_n \in \Sigma$, alors $|w|_z$ est le
+cardinal de l'ensemble $\{i : x_i = z\}$. On peut remarquer qu'on a :
+$|w| = \sum_{z\in\Sigma} |w|_z$ (i.e., la longueur de $w$ est la somme
+des nombres d'occurrences dedans des différentes lettres de
+l'alphabet).\par}
+
\subsection{Langages et opérations sur les langages}
\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
-qu'on ne demande pas que $L$ soit fini (mais il peut l'être).
+sous-ensemble (=une partie) de l'ensemble $\Sigma^*$ (de tous les mots
+sur $\Sigma$) : en symboles, $L \subseteq \Sigma^*$.
+
+On souligne qu'on ne demande pas que $L$ soit fini (mais il peut
+l'être, auquel cas on parlera fort logiquement de « langage fini »).
\thingy À titre d'exemple, l'ensemble $\{d,dc,dcc,dccc,dcccc,\ldots\}
= \{dc^r \colon r\in\mathbb{N}\}$ des mots formés d'un $d$ suivi d'un
@@ -536,7 +567,8 @@ a$ et $b^r = bbb\cdots b$.
\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
+\emph{quelconque} de mots appartenant à $L$, c'est-à-dire la réunion
+de tous les langages $L^r$ mentionnés ci-dessus :
\[
\begin{aligned}
L^* &:= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\
@@ -544,6 +576,11 @@ L^* &:= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\
\end{aligned}
\]
+À 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\}$.
+
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
@@ -575,6 +612,33 @@ 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
+
+\thingy De même que l'ensemble des mots sur un alphabet $\Sigma$ admet
+une notation, à savoir $\Sigma^*$, on peut introduire une notation
+pour l'ensemble de tous les \emph{langages} (= ensembles de mots)
+sur $\Sigma$ : ce sera $\mathscr{P}(\Sigma^*)$. Il s'agit d'un cas
+particulier de la construction « ensemble des parties » (si $E$ est un
+ensemble, $\mathscr{P}(E) = \{A : A\subseteq E\}$ est l'ensemble de
+tous les sous-ensembles de $A$ ; c'est un axiome de la théorie des
+ensembles qu'un tel ensemble existe bien). On pourrait donc écrire
+« $L \in \mathscr{P}(\Sigma^*)$ » comme 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.
+
+{\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
+ on préfère un élément de $\mathscr{P}(\mathscr{P}(\Sigma^*))$). On
+ ne développera pas de théorie générale des classes de langages et on
+ n'en parlera pas de façon systématique, mais on parlera de certaines
+ classes de langages importantes : la classe des langages rationnels
+ ou reconnaissables (§\ref{subsection-rational-languages} à
+ §\ref{section-recognizable-languages}), la classe des langages
+ algébriques (§\ref{section-context-free-grammars}), la classe des
+ langages décidables (§\ref{section-computability}) et la classe des
+ langages semi-décidable (\textit{ibid.}).\par}
+
\subsection{Langages rationnels et expressions rationnelles}\label{subsection-rational-languages}
@@ -866,7 +930,7 @@ régulière à utiliser est \texttt{\char"5C*} et que cette chaîne de
caractères s'écrit \texttt{"\char"5C\char"5C*"} en Java.
-\section{Automates finis}
+\section{Automates finis}\label{section-finite-automata}
\setcounter{comcnt}{0}
@@ -1786,7 +1850,7 @@ choix.
\par}
-\section{Langages reconnaissables et langages rationnels}
+\section{Langages reconnaissables et langages rationnels}\label{section-recognizable-languages}
\subsection{Stabilité des langages reconnaissables}
@@ -2878,7 +2942,7 @@ et les langages reconnus sont les mêmes.
\end{proof}
-\section{Grammaires hors contexte}
+\section{Grammaires hors contexte}\label{section-context-free-grammars}
\setcounter{comcnt}{0}
@@ -3357,7 +3421,7 @@ S\; \rightarrow\; aSbS \;|\; bSaS \;|\; \varepsilon
\varepsilon$) engendre le langage $L$ formé des mots ayant un nombre
total de $a$ égal au nombre total de $b$, i.e., $L = \{w \in\Sigma^* :
|w|_a = |w|_b\}$ où $|w|_x$ désigne le nombre total d'occurrences de
-la lettre $x$ dans le mot $w$.
+la lettre $x$ dans le mot $w$ (cf. \ref{number-of-occurrences-of-letter}).
Dans un sens il est évident que tout pseudo-mot obtenu en dérivant $S$
a un nombre de $a$ égal au nombre de $b$, puisque cette propriété est
@@ -4037,7 +4101,7 @@ construits (et éventuellement les arbres eux-mêmes).
%
%
-\section{Introduction à la calculabilité}
+\section{Introduction à la calculabilité}\label{section-computability}
\setcounter{comcnt}{0}