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