Démonstration du théorème du gonflement pour lg. réguliers

Pouêt pouêt,

J'essaie de trouver une démonstration du théorème du gonflement, mais dans le livre on n'aide pas beaucoup: «il suffit d'utiliser les observations de la section précédente».

J'y suis presque, mais il y a quand-même un détail qui coince.



Ce sont les deux dernières lignes qui ne vont pas: ne peut pas être vide

Si |w| = |Q|, alors dans ton chemin il y a |w|+1 états. Donc il y en a forcément un par lequel on passe deux fois (puisqu'on ne dispose que de |w| états). Le tronçon (non-vide) entre la première occurence de cet état et sa seconde occurence définit u. Comme le tronçon est non-vide, on a bien u != eps.

Bref, ça ne sert à rien de dissocier les cas

Ah oui, c'est vrai, pour un mot de 1 lettre, il faut 2 états, pour un mot de n lettres, il faut n+1 états.

Ok merci :-D