Bonjour à vous matheux/matheuses !
J'étudie en ce moment un cours intitulé Automates & Langages en autodidacte et qui dit autodidacte dit "pas de prof pour vous corrigé". Donc je viens vers vous en espérant que vous pourrez m'aider à avancer dans ce cours !
Le problème qui me fait butter aujourd'hui concerne la commutativité de la concaténation des mots, voici l'énoncé :
Soitet
deux mots de
Montrer queet
commutent si et seulement si il existe un mot
et deux entiers positifs ou nuls
et
tels que
et
. Pour => on pourra procéder par récurrence sur
.
Donc pour <= aucun problème c'est trivial, mais je n'arrive pas à voir cette fameuse récurrence ! Je ne vois pas comment utiliser une hypothèse de récurrence sur |u|+|v|= n vu que quand on passe à |u|+|v|=n+1, même si on trouve un mot (ou 2) mots avec une longueur n, rien ne dit que ces nouveau mots commuterons (exemple simple: u=ab v=abab alors u.v commutent, mais si on retire une lettre à u ou v ils ne commuterons plus.
Si vous pouvez me mettre sur la bonne piste avec quelque indices, je vous en serait infiniment reconnaissant !
Bien cordialement !
-----