Pumping lemma for algebraic languages.

1 files changed, 42 insertions, 1 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 98ed13c..84ff14d 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2346,7 +2346,7 @@ 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[(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}
@@ -3676,6 +3676,47 @@ l'intersection des deux, et ce sont ces mots qui forcent ce langage à
 être intrinsèquement ambigu.
 
 
+\subsection{Le lemme de pompage pour les langages algébriques}
+
+\begin{prop}[lemme de pompage pour les langages algébriques]\label{pumping-lemma-for-algebraic-languages}
+Soit $L$ un langage algébrique.  Il existe alors un entier $k$ tel que
+tout mot de $t \in L$ de longueur $|t| \geq k$ admette une
+factorisation $t = uvwxy$ en cinq facteurs $u,v,w,x,y$ où :
+\begin{itemize}
+\item[(i)] $|vx| \geq 1$ (c'est-à-dire $v\neq\varepsilon$ \emph{ou
+  bien} $x\neq\varepsilon$),
+\item[(ii)] $|vwx| \leq k$,
+\item[(iii)] pour tout $i\geq 0$ on a $uv^iwx^iy \in L$.
+\end{itemize}
+\end{prop}
+\begin{proof}\textcolor{red}{(Omise.)}\end{proof}
+
+Donnons maintenant un exemple d'utilisation du lemme :
+
+\begin{prop}\label{example-of-pumping-lemma-for-algebraic-languages}
+Soit $\Sigma = \{a,b,c\}$.  Le langage $L = \{a^n b^n c^n :
+n\in\mathbb{N}\} = \{\varepsilon, abc, aabbcc, aaabbbcc,\ldots\}$
+n'est pas algébrique.
+\end{prop}
+\begin{proof}
+Appliquons la proposition \ref{pumping-lemma-for-algebraic-languages}
+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 c^k$ :
+il doit alors exister une factorisation $t = uvwxy$ pour laquelle on a
+(i) $|vx|\geq 1$, (ii) $|vwx|\leq k$ et (iii) $uv^iwx^iy \in L$ pour
+tout $i\geq 0$.  La propriété (ii) assure que le facteur $vwx$ ne peut
+pas contenir simultanément les lettres $a$ et $c$ : en effet, tout
+facteur de $t$ comportant un $a$ et un $c$ doit avoir aussi le facteur
+$b^k$, et donc être de longueur $\geq k+2$.  Supposons que $vwx$ ne
+contienne pas la lettre $c$ (l'autre cas étant complètement
+analogue) : en particulier, ni $v$ ni $x$ ne la contient, donc le mot
+$uv^iwx^iy$, qui est dans $L$ d'après (iii), a le même nombre de $c$
+que le mot $t$ initial ; mais comme son nombre de $a$ ou bien de $b$
+est différent (d'après (i)), on a une contradiction.
+\end{proof}
+
+
+
 %
 %
 %