summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-inf105.tex12
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}