From b560f3a544e85a63de3dc8f14338b2824d9efeb3 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Wed, 1 Nov 2017 00:06:18 +0100
Subject: An intuitive explanation of the pumping lemma's uses.

---
 notes-inf105.tex | 12 ++++++++++++
 1 file changed, 12 insertions(+)

(limited to 'notes-inf105.tex')

diff --git a/notes-inf105.tex b/notes-inf105.tex
index b51e3c5..bbb8582 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3760,6 +3760,18 @@ 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}
 
+\thingy L'idée intuitive derrière la démonstration qu'on vient de
+faire est la suivante : un automate fini ne dispose que d'une quantité
+finie (bornée) de mémoire, donc ne peut « compter » que jusqu'à un
+nombre borné (au-delà, il va retomber sur un état déjà atteint par un
+plus petit nombre de $a$, et sera incapable de vérifier si le nombre
+de $b$ est égal).  C'est ce type de raisonnement que le lemme de
+pompage permet de formaliser.  Généralement parlant, on doit garder à
+l'esprit le fait que toutes sortes de langages ne sont pas rationnels
+pour la raison informelle que les identifier demande une quantité de
+mémoire qui pourrait être arbitrairement grande, et que pour le
+montrer rigoureusement, le lemme de pompage sera souvent utile.
+
 
 \subsection{L'automate minimal, et la minimisation}
 
-- 
cgit v1.2.3

