summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-11-01 00:06:18 +0100
committerDavid A. Madore <david+git@madore.org>2017-11-01 00:06:18 +0100
commitb560f3a544e85a63de3dc8f14338b2824d9efeb3 (patch)
treee090a65cde7a044c7c4f35394eebce1a5695359d
parent24527475fbf2fa526f8142edc08615ae73d94600 (diff)
downloadinf105-b560f3a544e85a63de3dc8f14338b2824d9efeb3.tar.gz
inf105-b560f3a544e85a63de3dc8f14338b2824d9efeb3.tar.bz2
inf105-b560f3a544e85a63de3dc8f14338b2824d9efeb3.zip
An intuitive explanation of the pumping lemma's uses.
-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}