From d0da92a1ce5565c8630896b2429b9d0b4dc812b6 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Wed, 9 Nov 2016 17:48:00 +0100
Subject: Rational languages and rational expressions.

---
 notes-inf105.tex | 127 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 127 insertions(+)

(limited to 'notes-inf105.tex')

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}
+
+
 %
 %
 %
-- 
cgit v1.2.3

