summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-30 20:03:55 +0100
committerDavid A. Madore <david+git@madore.org>2016-11-30 20:03:55 +0100
commit8d7c77c96249f7e7c0f167b9710b59efa5662010 (patch)
treeee001983b739a815db2209299f7747a105418c32 /notes-inf105.tex
parent25faa28bec81e4a829eda5d26521e849e1243a23 (diff)
downloadinf105-8d7c77c96249f7e7c0f167b9710b59efa5662010.tar.gz
inf105-8d7c77c96249f7e7c0f167b9710b59efa5662010.tar.bz2
inf105-8d7c77c96249f7e7c0f167b9710b59efa5662010.zip
Using the pumping lemma.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex177
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}
+
%
%