Using the pumping lemma.

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}
+
 
 %
 %