An intuitive explanation of the pumping lemma's uses.

1 files changed, 12 insertions, 0 deletions

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}