The pumping lemma.

1 files changed, 64 insertions, 1 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 6d60fe7..afcc0cd 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -941,7 +941,9 @@ au même (par récurrence sur la longueur du second argument) :
 \end{itemize}
 (en particulier, $\delta^*(q,x) = \delta(q,x)$ si $x\in\Sigma$, donc
 avec la convention faite en \ref{convention-on-words-of-length-one},
-on peut dire que $\delta^*$ prolonge $\delta$).
+on peut dire que $\delta^*$ prolonge $\delta$ ; il sera par ailleurs
+utile de remarquer que $\delta^*(q,ww') =
+\delta^*(\delta^*(q,w),w')$).
 
 Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$
 \textbf{accepte} ou \textbf{reconnaît} un mot $w$ lorsque
@@ -2224,6 +2226,67 @@ conduit à l'automate suivant :
 \noindent et finalement à l'expression rationnelle
 $(0|11|10(1|00){*}01){*}$, qui est équivalente à la précédente.
 
+\begin{cor}
+La classe des langages rationnels et celle des langages
+reconnaissables coïncident.  (On pourra donc considérer ces termes
+comme synonymes.)
+\end{cor}
+
+
+\subsection{Le lemme de pompage}
+
+\begin{prop}[lemme de pompage pour les langages rationnels]
+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ù :
+\begin{itemize}
+\item[(i)] $|v| \geq 1$ (c'est-à-dire $v\neq\varepsilon$,
+\item[(ii)] $|uv| \leq k$,
+\item[(iii)] pour tout $i\geq 0$ on a $uv^iw \in L$.
+\end{itemize}
+\end{prop}
+\begin{proof}
+Soit $A$ un DFA qui reconnaît $L$, et soit $k$ son nombre d'états : on
+va montrer que $k$ vérifie les propriétés énoncées.  Pour cela, soit
+$t = x_1 \cdots x_n$ un mot de $L$ de longueur $n \geq k$, et soient
+$q_0,\ldots,q_n$ les états traversés par $A$ pendant la consommation
+de $t$, autrement dit, $q_0$ est l'état initial, et $q_j =
+\delta(q_{j-1}, x_j)$ pour chaque $1\leq j\leq n$ ; l'état $q_n =
+\delta^*(q_0, t)$ est final puisque $t \in L$.  Comme $n+1 > k$ et
+comme l'automate $A$ a $k$ états, par le principe des tiroirs, il
+existe $j_1\neq j_2$ tels que $q_{j_1} = q_{j_2}$ : pour être plus
+précis, soit $j_2$ le plus petit possible tel que les états
+$q_0,\ldots,q_{j_2}$ ne soient pas tous distincts, autrement dit, le
+premier état répété, et soit $j_1$ la précédente occurrence (forcément
+unique) de cet état, c'est-à-dire l'indice tel que $j_1<j_2$ et
+$q_{j_1} = q_{j_2}$.
+
+Posons $u = x_1\cdots x_{j_1}$ (le préfixe de $t$ de longueur $j_1$,
+qui est le mot vide si $j_1 = 0$) et $v = x_{j_1+1}\cdots x_{j_2}$ (de
+longueur $j_2 - j_1$), et enfin $w = x_{j_2+1}\cdots x_n$ (le suffixe
+de $t$ de longueur $n-j_2$, avec la convention $w = \varepsilon$ si
+$j_2 = n$).  Ceci définit bien une factorisation $t = uvw$.
+
+On a bien (i) $|v| \geq 1$ puisque $j_2 > j_1$.  On a par ailleurs
+(ii) $|uv| \leq k$ puisque $|uv| = j_2$ et que les $j_2$ états
+$q_0,\ldots,q_{j_2-1}$ sont distincts (c'est la minimalité de $j_2$)
+de sorte que $j_2 \leq k$ (toujours par le principe des tiroirs).
+
+Montrons enfin (iii).  On rappelle tout d'abord que
+$\delta^*(q,x_1\cdots x_j) =\penalty0 \delta(\cdots\penalty500
+\delta(\delta(q,x_1),x_2)\cdots,x_j)$.  Remarquons que
+$\delta^*(q_0,u) = \delta^*(q_0,x_1\cdots x_{j_1}) = q_{j_1}$, et que
+$\delta^*(q_{j_1},v) = \delta^*(q_{j_1},x_{j_1+1}\cdots x_{j_2}) =
+q_{j_2} = q_{j_1}$.  De cette dernière égalité, on tire
+$\delta^*(q_{j_1},v^i) = q_{j_1}$ pour tout $i \geq 0$ (par récurrence
+sur $i$).  Enfin, $\delta^*(q_{j_1},w) = \delta^*(q_{j_2},w) =
+\delta^*(q_{j_2}, x_{j_2+1}\cdots x_n) = q_n$ (qui est un état final).
+En mettant ces faits ensemble, on a $\delta^*(q_0, uv^iw) =
+\delta^*(q_{j_1}, v^iw) = \delta^*(q_{j_1}, w) = q_n$, et puisque
+$q_n$ est final, ceci montre que le mot $uv^iw$ est accepté par $A$,
+i.e., $uv^iw \in L$.
+\end{proof}
+
 
 %
 %