From b560f3a544e85a63de3dc8f14338b2824d9efeb3 Mon Sep 17 00:00:00 2001 From: "David A. Madore" 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