summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-10 15:21:58 +0100
committerDavid A. Madore <david+git@madore.org>2017-01-10 15:21:58 +0100
commit87df1b27a05d9192093b5d14a32da1dacc1a0d42 (patch)
treefcbc825392c6f878d86ed136fb4e2381d3171ea2 /notes-inf105.tex
parent029a75c66768c84e1a10b7e364f564cf0249a3e5 (diff)
downloadinf105-87df1b27a05d9192093b5d14a32da1dacc1a0d42.tar.gz
inf105-87df1b27a05d9192093b5d14a32da1dacc1a0d42.tar.bz2
inf105-87df1b27a05d9192093b5d14a32da1dacc1a0d42.zip
Pumping lemma for algebraic languages.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex43
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}
+
+
+
%
%
%