diff options
| -rw-r--r-- | notes-inf105.tex | 127 |
1 files changed, 127 insertions, 0 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 03f7f57..e503f19 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -454,6 +454,10 @@ L_1 L_2 &= \{w_1 w_2 : w_1 \in L_1,\, w_2 \in L_2\}\\ \end{aligned} \] +À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, si on a $L_1 += \{a,bb\}$ et $L_2 = \{bc, cd\}$ alors $L_1 L_2 = \{abc, acd, bbbc, +bbcd\}$. + \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 @@ -465,6 +469,10 @@ récurrence : \item $L^{r+1} = L^r L$. \end{itemize} +À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, si on a $L = +\{a,bb\}$, alors $L^2 = \{aa, abb, bba, bbbb\}$ et $L^3 = \{aaa, aabb, +abba, abbbb, \penalty-100 bbaa, bbabb, bbbba, bbbbbb\}$. + \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 @@ -510,6 +518,125 @@ qu'il ne contient pas $\varepsilon$ ; tandis que si $\varepsilon$ appartient déjà à $L$, alors $L^+$ est égal à $L^*$. +\subsection{Langages rationnels et expressions rationnelles} + +\thingy Soit $\Sigma$ un alphabet. On va considérer les langages +de base triviaux suivants : +\begin{itemize} +\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$, +\end{itemize} +et on va les combiner par les opérations dites « rationnelles » +suivantes : +\begin{itemize} +\item la réunion $(L_1,L_2) \mapsto L_1 \cup L_2$, +\item la concaténation $(L_1,L_2) \mapsto L_1 L_2$, et +\item l'étoile de Kleene $L \mapsto L^*$. +\end{itemize} + +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). + +À 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, +c'est-à-dire $\{c\}^* = \{\varepsilon, c, cc, ccc, cccc,\ldots\}$, est +rationnel, et comme $\{d\}$ l'est aussi, la concaténation +$\{d\}(\{c\}^*) = \{d, dc, dcc, dccc, \ldots\}$ est encore un langage +rationnel. + +\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. + +Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$) +est un mot sur l'alphabet $\Sigma \cup \{\bot, +\underline{\varepsilon}, {(}, {)}, {|}, {*}\}$, où $\bot, +\underline{\varepsilon}, {(}, {)}, {|}, {*}$ sont de nouveaux +caractères \emph{n'appartenant pas} à l'alphabet $\Sigma$, appelés +\textbf{métacaractères}, et qui servent à marquer la manière dont est +formée l'expression rationnelle. On définit simultanément la notion +d'expression rationnelle $r$ et de \textbf{langage désigné} $L_r$ par +l'expression $r$, de la manière suivante : +\begin{itemize} +\item $\bot$ est une expression rationnelle et son langage désigné + est $L_\bot := \varnothing$, +\item $\underline{\varepsilon}$ est une expression rationnelle et son + langage désigné est $L_{\underline{\varepsilon}} := + \{\varepsilon\}$, +\item si $x\in\Sigma$ est une lettre de l'alphabet $\Sigma$, alors le + mot $x$ est une expression rationnelle et son langage désigné + est $L_x := \{x\}$, +\item si $r_1,r_2$ sont deux expressions rationnelles et $L_1 = + L_{r_1}$ et $L_2 = L_{r_2}$ les langages désignés correspondants, + alors $r_1 r_2$ est une expression rationnelle et son langage + désigné est $L_{r_1 r_2} := L_1 L_2$, +\item si $r_1,r_2$ sont deux expressions rationnelles et $L_1 = + L_{r_1}$ et $L_2 = L_{r_2}$ les langages désignés correspondants, + alors $(r_1|r_2)$ est une expression rationnelle et son langage + désigné est $L_{(r_1|r_2)} := L_1\cup L_2$, +\item si $r$ est une expression rationnelle et $L = L_r$ les langage + désigné correspondant, alors $(r)*$ est une expression rationnelle + et son langage désigné est $L_{(r)*} := L^*$. +\end{itemize} + +À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, $c$ est une +expression rationnelle qui désigne le langage $\{c\}$, donc $(c)*$ en +est une qui désigne le langage $\{c\}^* = \{\varepsilon, c, cc, +ccc,\ldots\}$, et enfin $d(c)*$ en est une qui désigne le langage $\{d, +dc, dcc, \ldots\}$ des mots formés d'un $d$ et d'une succession +quelconques de $c$. Voici quelques autres exemples, toujours sur +$\Sigma = \{a,b,c,d\}$ : +\begin{itemize} +\item l'expression rationnelle $(a|b)$ désigne le langage $\{a\} \cup + \{b\} = \{a,b\}$ formé des deux mots d'une seule lettre $a$ et $b$ ; +\item l'expression rationnelle $(a|b)c$ désigne le langage + $\{a,b\}\{c\} = \{ac,bc\}$, de même que $(ac|bc)$ ; +\item l'expression rationnelle $(bc)*$ désigne le langage $\{bc\}^* = + \{\varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ; +\item l'expression rationnelle $(a|(bc)*)$ désigne le langage $\{a\} + \cup \{bc\}^* = \{a, \varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ; +\item l'expression rationnelle $(a|(bc)*)d$ désigne le langage $\{a, d, + bcd, bcbcd, bcbcbcd, \ldots\}$. +\end{itemize} + +Un langage rationnel est par définition 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$ +lorsque ce mot appartient au langage qu'elle désigne (i.e., $w \in +L_r$). Par exemple, $dccc$ vérifie l'expression rationnelle $d(c)*$. + +La convention de parenthésage introduite ci-dessus est inambiguë mais +parfois inutilement lourde : on se permettra parfois de l'alléger, par +exemple d'écrire $(r_1|r_2|r_3)$ pour $((r_1|r_2)|r_3)$ (ou pour +$(r_1|(r_2|r_3))$, ce qui n'a guère d'importance vu qu'elles désignent +le même langage), ou encore $x*$ pour $(x)*$ lorsque $x$ est formé +d'un seul caractère. La convention essentielle est que l'opération +d'étoile $*$ est la plus prioritaire ($ab*$ se lit comme $a(b)*$ et +non pas comme $(ab)*$), la concaténation vient après, et la barre de +disjonction $|$ est la moins prioritaire ($ab|cd$ se lit comme +$(ab|cd)$ et pas comme $a(b|c)d$). + +{\footnotesize Les métacaractères $\bot$ et $\underline{\varepsilon}$ + sont introduits ici par souci de complétude mais font rarement + utilisés dans les expressions rationnelles (le métacaractère + $\underline{\varepsilon}$ a été souligné parce qu'il s'agit d'une + vraie lettre et non pas du mot vide ; on peut ignorer cette + subtilité qui n'a que très peu d'importance).\par} + + % % % |