Langages formels, Automates fini

[Mikiisa]

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é :

Soit et deux mots de

Montrer que et 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 !
-----