Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité

La longueur de la concaténation de deux mots est la somme des longueurs individuelles

 

La longueur de la concaténation de deux mots est la somme des longueurs individuelles

Soit u et v sont des mots, alors la longueur de leur concaténation est la somme des longueurs individuelles, c'est-à-dire, $$|uv|=|u|+|v|$$

Démonstration

Pour prouver cette propriété, nous avons d'abord besoin d'une définition de la longueur d'une chaîne. On fait une telle définition de manière récursive : $$|a|=1$$ $$|wa|=|w|+1$$ pour tout \(a \in \Sigma\) et tout mot w sur \(\Sigma\). Cette définition est une déclaration formelle de notre compréhension intuitive de la longueur d'un mot : la longueur d'un seul symbole est de un, et la longueur de tout mot est augmentée de un si nous y ajoutons un autre symbole.

On peut prouver la propriété par induction.

Cas de base

Par définition, la propriété est valable pour tous les u de longueur quelconque et tous les v de longueur 1, donc le cas de base est vérifié.

Etape inductive

Par hypothèse inductive, nous considérons que la propriété est valable pour tous les u de longueur quelconque et tous les v de longueur 1, 2, ..., n.

Prenons maintenant tout v de longueur n+1 et écrivons-le sous la forme \(v = wa\). Alors, $$|v|=|w|+1$$ $$|uv|=|uwa|=|uw|+1$$

Par l'hypothèse inductive (qui est applicable puisque w est de longueur n), $$|uw|=|u|+|w|,$$ de telle sorte que $$|uv|=|u|+|w|+1 = |u|+|v|$$

Par conséquent, la propriété est valable pour tous les u et tous les v de longueur inférieure ou égale à n+1.


Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.