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.