diff options
| -rw-r--r-- | notes-inf105.tex | 64 |
1 files changed, 36 insertions, 28 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 67b31ec..0b9e751 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -613,61 +613,61 @@ est un mot sur l'alphabet $\Sigma \cup \{\bot, 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 : +d'expression rationnelle $r$ et de \textbf{langage dénoté} (ou +\textbf{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é +\item $\bot$ est une expression rationnelle et son langage dénoté est $L_\bot := \varnothing$, \item $\underline{\varepsilon}$ est une expression rationnelle et son - langage désigné est $L_{\underline{\varepsilon}} := + langage dénoté 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é + mot $x$ est une expression rationnelle et son langage dénoté 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, + L_{r_1}$ et $L_2 = L_{r_2}$ les langages dénoté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$, + dénoté 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, + L_{r_1}$ et $L_2 = L_{r_2}$ les langages dénoté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$, + dénoté 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^*$. + dénoté correspondant, alors $(r){*}$ est une expression rationnelle + et son langage dénoté 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, +expression rationnelle qui dénote le langage $\{c\}$, donc $(c){*}$ en +est une qui dénote le langage $\{c\}^* = \{\varepsilon, c, cc, +ccc,\ldots\}$, et enfin $d(c){*}$ en est une qui dénote 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 +\item l'expression rationnelle $(a|b)$ dénote 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 +\item l'expression rationnelle $(a|b)c$ dénote le langage $\{a,b\}\{c\} = \{ac,bc\}$, de même que $(ac|bc)$ ; -\item l'expression rationnelle $(bc){*}$ désigne le langage $\{bc\}^* = +\item l'expression rationnelle $(bc){*}$ dénote le langage $\{bc\}^* = \{\varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ; -\item l'expression rationnelle $(a|(bc){*})$ désigne le langage $\{a\} +\item l'expression rationnelle $(a|(bc){*})$ dénote le langage $\{a\} \cup \{bc\}^* = \{a, \varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ; -\item l'expression rationnelle $(a|(bc){*})d$ désigne le langage $\{a, d, +\item l'expression rationnelle $(a|(bc){*})d$ dénote le langage $\{a, d, bcd, bcbcd, bcbcbcd, \ldots\}$. \end{itemize} Un langage rationnel est par construction la même chose qu'un langage -pour lequel il existe une expression rationnelle qui le désigne. +pour lequel il existe une expression rationnelle qui le dénote. 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 +lorsque ce mot appartient au langage qu'elle dénote (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 +$(r_1|(r_2|r_3))$, ce qui n'a guère d'importance vu qu'elles dénotent 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 @@ -686,9 +686,17 @@ La barre de disjonction que nous avons notée ${|}$ est souvent plutôt notée $+$ par les mathématiciens. Il y a ici un risque de confusion lié au fait que, en informatique, le symbole \texttt{+} est utilisé par de nombreux moteurs d'expressions régulières (par exemple, -\texttt{egrep}) pour désigner l'opération évoquée en \ref{kleene-plus} +\texttt{egrep}) pour dénoter l'opération évoquée en \ref{kleene-plus} (de sorte que $r+$ a le même sens que $rr{*}$). +\thingy Deux expressions rationnelles $r_1,r_2$ sont dites +\textbf{équivalentes} lorsqu'elles dénotent le même langage. À titre +d'exemple, sur l'alphabet $\{a,b\}$, les deux expressions rationnelles +$(ab)*a$ et $a(ba)*$ sont équivalentes (toutes les deux dénotent le +langage $\{a, aba, ababa, \ldots\}$ formé des mots commençant et +finissant par un $a$ et dans lesquels chaque paire de $a$ est séparée +par un unique $b$). + \section{Automates finis} @@ -851,7 +859,7 @@ Cette description rend claire le fait que l'automate en question accepte exactement les mots contenant un $a$ suivi, pas forcément immédiatement, d'un $b$ ; autrement dit, les mots dont $ab$ est un sous-mot (cf. \ref{definition-subword}). Ce langage est donc -reconnaissable. (Il est aussi rationnel puisque désigné par +reconnaissable. (Il est aussi rationnel puisque dénoté par l'expression rationnelle $(b|c){*}a(b|c){*}b(a|b|c){*}$.) \thingy\label{definition-dfa-accessible-state} Un état $q$ d'un DFA @@ -991,7 +999,7 @@ quelconque de $c$. %%% end example2b %%% \end{center} -(Ce langage est aussi désigné par l'expression rationnelle +(Ce langage est aussi dénoté par l'expression rationnelle $c{*}ac{*}bc{*}$.) \begin{prop}\label{completion-of-dfai} @@ -1191,7 +1199,7 @@ Cet automate n'est pas déterministe car il existe deux transitions étiquetées $a$ partant de l'état $0$. En considérant les différents chemins possibles entre $0$ et $2$ dans ce graphe, on comprend que le langage qu'il reconnaît est le langage des mots sur $\{a,b\}$ dont -l'avant-dernière lettre est un $a$ (c'est aussi le langage désigné par +l'avant-dernière lettre est un $a$ (c'est aussi le langage dénoté par l'expression rationnelle $(a|b){*}a(a|b)$). Une façon de présenter le non-déterminisme est que l'automate « devine », quand il est dans l'état $0$ et qu'on lui fait consommer un $a$, si ce $a$ sera @@ -1447,7 +1455,7 @@ En considérant les différents chemins possibles entre $0$ et $2$ sur ce graphe, on comprend que le langage qu'il reconnaît est celui des mots sur $\{a,b,c\}$ formés d'un nombre quelconque de $a$ suivi d'un nombre quelconque de $b$ suivi d'un nombre quelconque de $c$, ou, si -on préfère, le langage désigné par l'expression rationnelle +on préfère, le langage dénoté par l'expression rationnelle $a{*}b{*}c{*}$. \thingy Si $q$ est un état d'un εNFA, on appelle \textbf{ε-fermeture} @@ -1774,7 +1782,7 @@ de $A$ en question vers $q_0$. On a donc bien $L_{A'} = L^*$. \begin{prop}\label{rational-languages-are-recognizable} Tout langage rationnel est reconnaissable ; de plus, un εNFA le reconnaissant se déduit algorithmiquement d'une expression rationnelle -le désignant. +le dénotant. \end{prop} \begin{proof} Cela résulte de façon évidente de la définition des langages |