diff options
| -rw-r--r-- | notes-inf105.tex | 71 |
1 files changed, 66 insertions, 5 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index d62cbbe..5fce7d4 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -185,11 +185,12 @@ 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$. -\thingy Si le cardinal de l'alphabet $\Sigma$ vaut $\#\Sigma = N$, -alors, pour chaque $n$, le nombre de mots de longueur exactement $n$ -est égal à $N^n$ (combinatoire classique). Le nombre de mots de -longueur $\leq n$ vaut donc $1 + N + \cdots + N^n = -\frac{N^{n+1}-1}{N-1}$ (somme d'une série géométrique). +\thingy\label{number-of-words-of-length-n} Si le cardinal de +l'alphabet $\Sigma$ vaut $\#\Sigma = N$, alors, pour chaque $n$, le +nombre de mots de longueur exactement $n$ est égal à $N^n$ +(combinatoire classique). Le nombre de mots de longueur $\leq n$ vaut +donc $1 + N + \cdots + N^n = \frac{N^{n+1}-1}{N-1}$ (somme d'une série +géométrique). \subsection{Concaténation de mots, préfixes, suffixes, facteurs, sous-mots} @@ -246,6 +247,24 @@ signifie exactement ce qui vient d'être dit). appliquant cette propriété à la fonction $\psi(x) = 1$ pour tout $x\in\Sigma$.\par} +\thingy Lorsque $w \in \Sigma^*$ et $r \in \mathbb{N}$, on définit un +mot $w^r$ comme la concaténation de $r$ facteurs tous égaux au +mot $w$, autrement dit, comme la répétition $r$ fois du mot $w$. +Formellement, on définit par récurrence : +\begin{itemize} +\item $w^0 = \varepsilon$ (le mot vide), +\item $w^{r+1} = w^r w$. +\end{itemize} +(Ces définitions valent, d'ailleurs, dans n'importe quel monoïde. On +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|$. + +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.) + \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 dira également : @@ -318,6 +337,48 @@ a$ et $u_1 = bb$ et $v_2 = c$ et $u_2 = a$ et $v_3 = b$ et $u_3 = \varepsilon$). +\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). + +\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 +nombre quelconque (éventuellement nul) de $c$ est un langage sur +l'alphabet $\Sigma = \{a,b,c,d\}$. On verra plus loin que ce langage +est « rationnel » (et pourra être désigné par l'expression rationnelle +$dc*$). + +Voici quelques autres exemples de langages : +\begin{itemize} +\item Le langage (fini) $\{foo,bar,baz\}$ formé des seuls trois mots + $foo$, $bar$, $baz$ sur l'alphabet $\Sigma = \{a,b,f,o,r,z\}$. +\item Le langage (fini) formé des mots de longueur exactement $42$ 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 (fini) formé 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 sur l'alphabet $\Sigma=\{a\}$ formé de tous les mots + dont la longueur est un nombre premier ($L = \{aa, aaa, a^5, a^7, + a^{11},\ldots\}$). Ce langage est infini. +\item Le langage sur l'alphabet $\Sigma=\{0,1\}$ formé de tous les + mots commençant par un $1$ et qui, interprétés comme un nombre écrit + en binaire, désignent un nombre premier ($L = \{10, 11, 101, 111, + 1011, \ldots\}$). +\item Le langage sur l'alphabet Unicode formé de tous les mots qui + constituent un document XML bien-formé d'après la spécification + XML 1.0. +\end{itemize} + + % % % |