diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 130 |
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} |