diff options
| -rw-r--r-- | notes-inf105.tex | 36 |
1 files changed, 28 insertions, 8 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 5ed7719..d1e43da 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -538,7 +538,7 @@ de base triviaux suivants : \item le langage vide $\varnothing$, \item le langage formé du seul mot vide, $\{\varepsilon\}$, et \item les langages formés d'un seul mot lui-même formé d'une seule - lettre, $\{a\}$ pour chaque $a\in\Sigma$, + lettre, $\{x\}$ pour chaque $x\in\Sigma$, \end{itemize} et on va les combiner par les opérations dites « rationnelles » suivantes : @@ -552,11 +552,11 @@ On obtient ainsi une certaine famille de langages (cf. ci-dessous pour une définition plus précise), qu'on appelle \textbf{langages rationnels} : les langages rationnels sont exactement ceux qui peuvent s'obtenir à partir des langages de base énumérés ci-dessus par -application des opérations qu'on vient de dire (i.e., la réunion de -deux langages rationnels, ou la concaténation de deux langages -rationnels, ou l'étoile de Kleene d'un langage rationnel, sont -rationnels, et les langages rationnels sont exactement ceux qu'on -obtient ainsi). +application (un nombre fini de fois) des opérations qu'on vient de +dire (i.e., la réunion de deux langages rationnels, ou la +concaténation de deux langages rationnels, ou l'étoile de Kleene d'un +langage rationnel, sont rationnels, et les langages rationnels sont +exactement ceux qu'on obtient ainsi). À titre d'exemple, sur l'alphabet $\{a,b,c,d\}$, comme le langage $\{c\}$ (formé du seul mot $c$) est rationnel, son étoile de Kleene, @@ -565,12 +565,32 @@ rationnel, et comme $\{d\}$ l'est aussi, la concaténation $\{d\}(\{c\}^*) = \{d, dc, dcc, dccc, \ldots\}$ est encore un langage rationnel. +{\footnotesize\thingy Formellement, la définition des langages + rationnelles est la suivante : un ensemble $\mathscr{C} \subseteq + \mathscr{P}(\Sigma^*)$ de langages (où $\mathscr{P}(\Sigma^*)$ est + l'ensemble des parties de $\Sigma^*$, i.e., l'ensemble de tous les + langages sur $\Sigma$) est dit \emph{stable par opérations + rationnelles} lorsqu'il est stable par les opérations de réunion, + concaténation et étoile de Kleene, i.e., si $L_1,L_2 \in + \mathscr{C}$ alors $L_1\cup L_2 \in \mathscr{C}$ et $L_1 L_2 \in + \mathscr{C}$, et si $L \in \mathscr{C}$ alors $L^* \in + \mathscr{C}$ ; le \emph{plus petit} (pour l'inclusion) ensemble de + langages stable par opérations rationnelles et contenant les + langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ pour $x \in + \Sigma$ (i.e. $\varnothing\in\mathscr{C}$, $\{\varepsilon\} \in + \mathscr{C}$ et si $x\in\Sigma$ alors $\{x\}\in\mathscr{C}$), ou + plus exactement, l'intersection de tous les ensembles $\mathscr{C}$ + vérifiant tous ces propriétés, est la classe $\mathscr{R}$ des + langages rationnels. \par} + \thingy Pour décrire la manière dont un langage rationnel est fabriqué (à partir des langages de base par les opérations rationnelles), comme il est malcommode d'écrire quelque chose comme $\{d\}(\{c\}^*)$, on 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. +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*$. Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$) est un mot sur l'alphabet $\Sigma \cup \{\bot, @@ -623,7 +643,7 @@ $\Sigma = \{a,b,c,d\}$ : bcd, bcbcd, bcbcbcd, \ldots\}$. \end{itemize} -Un langage rationnel est par définition la même chose qu'un langage +Un langage rationnel est par construction la même chose qu'un langage pour lequel il existe une expression rationnelle qui le désigne. On dira qu'un mot $w$ \textbf{vérifie} une expression rationnelle $r$ |