From 85eb25e585c01eba5af5360e93c3c8f13218efe9 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 7 Nov 2016 23:27:25 +0100 Subject: More about languages. --- notes-inf105.tex | 110 +++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 106 insertions(+), 4 deletions(-) diff --git a/notes-inf105.tex b/notes-inf105.tex index 5fce7d4..400e6a0 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -247,10 +247,10 @@ 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 : +\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$ +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$. @@ -366,6 +366,15 @@ Voici quelques autres exemples de langages : 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,b\}$ formé des mots qui + commencent par trois $a$ consécutifs : ou, si on préfère, qui ont le + mot $aaa$ comme préfixe. +\item Le langage sur l'alphabet $\Sigma=\{a,b\}$ formé des mots qui + contiennent trois $a$ consécutifs ; ou, si on préfère, qui ont $aaa$ + comme facteur. +\item Le langage sur l'alphabet $\Sigma=\{a,b\}$ formé des mots qui + contiennent au moins trois $a$, non nécessairement consécutifs ; ou, + si on préfère, qui ont $aaa$ comme sous-mot. \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. @@ -378,6 +387,99 @@ Voici quelques autres exemples de langages : XML 1.0. \end{itemize} +\thingy On pourrait aussi considérer un langage (sur +l'alphabet $\Sigma$) comme une \emph{propriété} des mots (sur +l'alphabet en question). Précisément, si $P$ est une propriété qu'un +mot $w \in \Sigma^*$ peut ou ne pas avoir, on considère le langage +$L_P = \{w \in \Sigma^* : w \text{~a la propriété~} P\}$, et +inversement, si $L \subseteq \Sigma^*$ est un langage, on considère la +propriété « appartenir à $L$ » : en identifiant la propriété et le +langage qu'on vient d'associer l'un à l'autre (par exemple, le langage +des mots commençant par $a$ et la propriété « commencer par $a$ »), un +langage pourrait être considéré comme une propriété des mots. + +{\footnotesize(Ceci n'a rien de spécifique aux langages : une partie + d'un ensemble $E$ quelconque peut être identifiée à une propriété + que les éléments de $E$ peuvent ou ne pas avoir, à savoir, + appartenir à la partie en question.)\par} + +On évitera de faire cette identification pour ne pas introduire de +confusion, mais il est utile de la garder à l'esprit : par exemple, +dans un langage de programmation fonctionnel, un « langage » au sens +de ces notes peut être considéré comme une fonction (pure, +c'est-à-dire, déterministe et sans effet de bord) prenant en entrée +une chaîne de caractères et renvoyant un booléen. + +\thingy Si $L_1$ et $L_2$ sont deux langages sur un même +alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on +peut former les langages \textbf{union} $L_1\cup L_2$ et +\textbf{intersection} $L_1\cap L_2$ qui sont simplement les opérations +ensemblistes usuelles (entre parties de $\Sigma^*$). + +Les opérations correspondantes sur les propriétés de mots sont +respectivement le « ou logique » (=disjonction) et le « et logique » +(=conjonction) : à titre d'exemple, sur $\Sigma = \{a,b\}$ si $L_1$ +est le langage des mots commençant par $a$ et $L_2$ le langage des +mots finissant par $b$, alors $L_1 \cup L_2$ est le langage des mots +commençant par $a$ \emph{ou bien} finissant par $b$, tandis que $L_1 +\cap L_2$ est le langage des mots commençant par $a$ \emph{et} +finissant par $b$. + +\thingy Si $L$ est un langage sur l'alphabet $\Sigma$, autrement dit +$L \subseteq \Sigma^*$, on peut former le langage $\Sigma^*\setminus +L$, parfois noté simplement $\overline L$ si ce n'est pas ambigu, dit +\textbf{complémentaire} de $L$, et qui est simplement l'ensemble des +mots sur $\Sigma$ \emph{n'appartenant pas} à $L$. L'opération +correspondante sur les propriétés de mots est la négation logique. + +À titre d'exemple, sur $\Sigma=\{a,b\}$, si $L$ est le langage des +mots commençant par $a$, alors $\overline{L}$ est le langage des mots +ne commençant pas par $a$, c'est-à-dire, la réunion de +$\{\varepsilon\}$ et du langage des mots commençant par $b$ (car sur +$\Sigma=\{a,b\}$, un mot ne commençant pas par $a$ est vide ou bien +commence par $b$). + +\thingy Si $L_1$ et $L_2$ sont deux langages sur un même +alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on +peut former le langage \textbf{concaténation} $L_1 L_2$ : il est +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\}\\ + &= \{w \in \Sigma^* : \exists w_1 \in L_1\, \exists w_2 \in L_2\,(w = w_1 w_2)\}\\ +\end{aligned} +\] + +\thingy Si $L$ est un langage sur l'alphabet $\Sigma$, autrement dit +$L \subseteq \Sigma^*$, et si $r \in \mathbb{N}$, on peut définir un +langage $L^r$, par analogie avec \ref{powers-of-a-word}, comme le +langage $L^r = \{w_1\cdots w_r : w_1,\ldots,w_r \in L\}$ formé des +concaténation de $r$ mots appartenant à $L$, ou si on préfère, par +récurrence : +\begin{itemize} +\item $L^0 = \{\varepsilon\}$, +\item $L^{r+1} = L^r L$. +\end{itemize} + +\emph{Attention}, $L^r$ n'est pas le langage $\{w^r : w\in L\}$ formé +des répétitions $r$ fois ($w^r$) des mots $w$ de $L$ : c'est le +langage des concaténations de $r$ mots appartenant à $L$ \emph{mais + ces mots peuvent être différents}. À titre d'exemple, si $L = +\{a,b\}$ alors $L^r$ est le langage formé des $2^r$ mots de longueur +exactement $r$ sur $\Sigma = \{a,b\}$, ce n'est pas l'ensemble à deux +éléments $\{a^r, b^r\}$ formé des seuls deux mots $a^r = aaa\cdots a$ +et $b^r = bbb\cdots b$. + +On définit enfin l'\textbf{étoile de Kleene} $L^*$ sur le langage $L$ +comme le langage formé des concaténations d'un nombre +\emph{quelconque} de mots appartenant à $L$, c'est-à-dire +\[ +\begin{aligned} +L^* &= \bigcup_{r=0}^{+\infty} L^r\\ +&= \{w_1\cdots w_r : r\in\mathbb{N},\, w_1,\ldots,w_r\in L\}\\ +\end{aligned} +\] % % -- cgit v1.2.3