diff options
| -rw-r--r-- | notes-inf105.tex | 177 |
1 files changed, 128 insertions, 49 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index afcc0cd..7b31806 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -373,39 +373,39 @@ $dc{*}$). Voici quelques autres exemples de langages : \begin{itemize} -\item Le langage (fini) $\{foo,bar,baz\}$ formé des seuls trois mots - $foo$, $bar$, $baz$ sur l'alphabet $\Sigma = \{a,b,f,o,r,z\}$. -\item Le langage (fini) formé des mots de longueur exactement $42$ sur - l'alphabet $\Sigma = \{p,q,r\}$. Comme on l'a vu +\item Le langage (fini) $\{foo,bar,baz\}$ constitué des seuls trois + mots $foo$, $bar$, $baz$ sur l'alphabet $\Sigma = \{a,b,f,o,r,z\}$. +\item Le langage (fini) constitué des mots de longueur exactement $42$ + sur l'alphabet $\Sigma = \{p,q,r\}$. Comme on l'a vu en \ref{number-of-words-of-length-n}, cet ensemble a pour cardinal exactement $3^{42}$. -\item Le langage (fini) formé du seul mot vide (=mot de longueur +\item Le langage (fini) constitué du seul mot vide (=mot de longueur exactement $0$) sur l'alphabet, disons, $\Sigma = \{p,q,r\}$. Ce langage $\{\varepsilon\}$ a pour cardinal $1$ (ou $3^0$ si on veut). 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 formé des mots de une seule lettre sur un alphabet +\item Le langage constitué des mots de une seule lettre sur un alphabet $\Sigma$, qu'on peut identifier à $\Sigma$ lui-même (en identifiant un mot de une lettre à la lettre en question). -\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. -\item Le langage sur l'alphabet $\Sigma=\{0,1\}$ formé de tous les +\item Le langage sur l'alphabet $\Sigma=\{a,b\}$ constitué 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\}$ constitué 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\}$ constitué 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\}$ constitué 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. +\item Le langage sur l'alphabet $\Sigma=\{0,1\}$ constitué de tous les mots commençant par un $1$ et qui, interprétés comme un nombre écrit en binaire, désignent un nombre premier ($L = \{10, 11, 101, 111, 1011, \ldots\}$). -\item Le langage sur l'alphabet Unicode formé de tous les mots qui - constituent un document XML bien-formé d'après la spécification +\item Le langage sur l'alphabet Unicode constitué de tous les mots qui + représentent un document XML bien-formé d'après la spécification XML 1.0. \end{itemize} @@ -480,7 +480,7 @@ 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 -langage $L^r = \{w_1\cdots w_r : w_1,\ldots,w_r \in L\}$ formé des +langage $L^r = \{w_1\cdots w_r : w_1,\ldots,w_r \in L\}$ constitué des concaténation de $r$ mots appartenant à $L$, ou si on préfère, par récurrence : \begin{itemize} @@ -492,19 +492,19 @@ récurrence : \{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 +\emph{Attention}, $L^r$ n'est pas le langage $\{w^r : w\in L\}$ +constitué 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 $\{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$. +\{a,b\}$ alors $L^r$ est le langage constitué des $2^r$ mots de +longueur exactement $r$ sur $\{a,b\}$, ce n'est pas l'ensemble à deux +éléments $\{a^r, b^r\}$ constitué des seuls deux mots $a^r = aaa\cdots +a$ et $b^r = bbb\cdots b$. \thingy Si $L$ est un langage sur l'alphabet $\Sigma$, on définit -enfin l'\textbf{étoile de Kleene} $L^*$ de $L$ comme le langage formé -des concaténations d'un nombre \emph{quelconque} de mots appartenant -à $L$, c'est-à-dire +enfin l'\textbf{étoile de Kleene} $L^*$ de $L$ comme le langage +constitué des concaténations d'un nombre \emph{quelconque} de mots +appartenant à $L$, c'est-à-dire \[ \begin{aligned} L^* &= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\ @@ -514,9 +514,9 @@ L^* &= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\ Comme ci-dessus, il faut souligner que les mots $w_1,\ldots,w_r$ concaténés n'ont pas à être égaux : notamment, $\{a,b\}^*$ est le -langage formé de tous les mots sur l'alphabet $\{a,b\}$, pas le -langage $\{a\}^* \cup \{b\}^*$ formé des mots obtenus en répétant la -lettre $a$ ou en répétant la lettre $b$. +langage constitué de tous les mots sur l'alphabet $\{a,b\}$, pas le +langage $\{a\}^* \cup \{b\}^*$ constitué des mots obtenus en répétant +la lettre $a$ ou en répétant la lettre $b$. On remarquera que la définition de $L^*$ ci-dessus redonne bien, lorsqu'on l'applique à l'alphabet $\Sigma$ lui-même (considéré comme @@ -550,8 +550,8 @@ c'est-à-dire $L^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L\}$. 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 +\item le langage constitué du seul mot vide, $\{\varepsilon\}$, et +\item les langages constitué d'un seul mot lui-même formé d'une seule lettre, $\{x\}$ pour chaque $x\in\Sigma$, \end{itemize} et on va les combiner par les opérations dites « rationnelles » @@ -573,11 +573,11 @@ langage rationnel, sont rationnels, et les langages rationnels sont exactement ceux qu'on obtient ainsi à partir des langages de base. À 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. +$\{c\}$ (constitué 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 Formellement, la définition des langages rationnelles est la suivante : un ensemble $\mathscr{C} \subseteq \mathscr{P}(\Sigma^*)$ @@ -597,8 +597,8 @@ propriétés, est la classe $\mathscr{R}$ des langages rationnels. \emph{Attention !}, le fait que la classe $\mathscr{R}$ des langages rationnels soit stable par concaténation signifie que si $L_1$ et -$L_2$ sont rationnels alors le langage $L_1 L_2$ (formé de tous les -mots concaténés d'un mot de $L_1$ et d'un mot de $L_2$) est +$L_2$ sont rationnels alors le langage $L_1 L_2$ (constitué de tous +les mots concaténés d'un mot de $L_1$ et d'un mot de $L_2$) est rationnel ; \emph{cela ne signifie pas} qu'un langage rationnel donné soit stable par concaténation (un langage stable $L$ par concaténation est un langage tel que si $w_1,w_2\in L$ alors $w_1 w_2 \in L$). @@ -652,7 +652,8 @@ quelconques de $c$. Voici quelques autres exemples, toujours sur $\Sigma = \{a,b,c,d\}$ : \begin{itemize} \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$ ; + \{b\} = \{a,b\}$ constitué des deux mots d'une seule lettre $a$ et + $b$ ; \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énote le langage $\{bc\}^* = @@ -683,9 +684,9 @@ L_r$). Par exemple, $dccc$ vérifie l'expression rationnelle $d(c){*}$. \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$). +le langage $\{a, aba, ababa, \ldots\}$ constitué des mots commençant +et finissant par un $a$ et dans lesquels chaque paire de $a$ est +séparée par un unique $b$). \thingy La convention de parenthésage introduite ci-dessus est inambiguë mais parfois inutilement lourde : on se permettra parfois de @@ -2235,7 +2236,17 @@ comme synonymes.) \subsection{Le lemme de pompage} -\begin{prop}[lemme de pompage pour les langages rationnels] +\thingy On ne dispose à ce stade-là d'aucun moyen pour montrer qu'un +langage \emph{n'est pas} rationnel. La +proposition \ref{pumping-lemma} qui va suivre, et qui s'appelle +couramment « lemme de pompage » (une traduction abusive de l'anglais +« pumping lemma ») constitue le moyen le plus fréquent permettant d'y +arriver : il énonce une condition \emph{nécessaire} pour qu'un langage +soit rationnel, si bien qu'on peut arriver à montrer qu'un langage +n'est pas rationnel en invalidant cette condition (généralement en +procédant par l'absurde). + +\begin{prop}[lemme de pompage pour les langages rationnels]\label{pumping-lemma} Soit $L$ un langage rationnel. Il existe alors un entier $k$ tel que tout mot de $t \in L$ de longueur $|t| \geq k$ admette une factorisation $t = uvw$ en trois facteurs $u,v,w$ où : @@ -2287,6 +2298,74 @@ $q_n$ est final, ceci montre que le mot $uv^iw$ est accepté par $A$, i.e., $uv^iw \in L$. \end{proof} +\thingy On attire l'attention sur l'alternation des quantificateurs. +Le lemme de pompage énonce le fait que : +\begin{itemize} +\item\emph{pour tout} langage rationnel $L$, +\item\emph{il existe} un entier $k\geq 0$ tel que +\item\emph{pour tout} mot $t\in L$ de longueur $|t|\geq k$, +\item\emph{il existe} une factorisation $t=uvw$ vérifiant les + propriétés (i) $|v|\geq 1$, (ii) $|uv|\leq k$ et (iii) qui suit : +\item\emph{pour tout} $i\geq 0$ on a $uv^iw \in L$. +\end{itemize} + +La complexité logique d'un énoncé étant justement mesurée par le +nombre d'alernations de quantificateurs (passages entre « pour tout » +et « il existe » ou vice versa), celui-ci mérite une attention +particulière. Rappelons donc, du point de vue logique, que, quand on +veut \emph{appliquer} un résultat de ce genre, on \emph{choisit + librement} les objets introduits par un quantificateur universel +(« pour tout »), mais \emph{on ne choisit pas} ceux qui sont +introduits par un quantificateur existentiel (« il existe ») (ces +derniers sont, si on veut, choisis par l'énoncé qu'on applique : on ne +fait que recevoir leur existence) ; les choses sont inversées quand on +doit démontrer un tel énoncé, mais la démonstration a été faite +ci-dessus et il est donc plus fréquent de devoir appliquer le lemme de +pompage. + +Le modèle d'une démonstration par l'absurde pour montrer qu'un langage +$L$ n'est pas rationnel est donc quelque chose comme ceci : +\begin{itemize} +\item on entame un raisonnement par l'absurde en supposant que $L$ est + rationnel, et on choisit $L$ pour appliquer le lemme de pompage + (parfois on l'applique à autre chose, comme l'intersection de $L$ + avec un langage connu pour être rationnel, mais en général ce + sera $L$), +\item le lemme de pompage fournit un $k$ (on \emph{ne choisit donc + pas} ce $k$, il est donné par le lemme), +\item on choisit alors un mot $t \in L$ de longueur $\geq k$, et c'est + là que réside la difficulté principale de la démonstration, +\item le lemme de pompage fournit une factorisation $t = uvw$, qu'on + \emph{ne choisit pas} non plus mais qu'on peut analyser, souvent en + utilisant (i) et (ii), +\item et on cherche à appliquer la propriété (iii), ce qui implique de + choisir un $i$, pour arriver à une contradiction (typiquement : le + mot $uv^i w$ n'est pas dans le langage alors qu'il est censé y + être). +\end{itemize} + +Donnons maintenant un exemple d'utilisation du lemme : + +\begin{prop} +Soit $\Sigma = \{a,b\}$. Le langage $L = \{a^n b^n : n\in\mathbb{N}\} += \{\varepsilon, ab, aabb, aaabbb,\ldots\}$ constitué des mots formés +d'un certain nombre ($n$) de $a$ suivis du même nombre de $b$ n'est +pas rationnel. +\end{prop} +\begin{proof} +Appliquons la proposition \ref{pumping-lemma} au langage $L$ +considéré : appelons $k$ l'entier dont le lemme de pompage garantit +l'existence. Considérons le mot $t := a^k b^k$ : il doit alors +exister une factorisation $t = uvw$ pour laquelle on a (i) $|v|\geq +1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in L$ pour tout $i\geq 0$. La +propriété (ii) assure que $uv$ est formé d'un certain nombre de +répétitions de la lettre $a$ : disons $u = a^\ell$ et $v = a^m$, si +bien que $w = a^{k-\ell-m} b^k$. La propriété (ii) donne $m\geq 1$. +Enfin, la propriété (iii) affirme que le mot $uv^iw = a^{k+(i-1)m} +b^k$ appartient à $L$ ; mais dès que $i\neq 1$, ceci est faux : il +suffit donc de prendre $i=0$ pour avoir une contradiction. +\end{proof} + % % |