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 :
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 sur la longueur de v.
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.
En effet, si \(|v| = 1\), alors \(v = a\) pour un certain symbole \(a \in \Sigma\). Par définition de la concaténation et de la longueur : \[ |uv| = |ua| = |u| + 1 = |u| + |v| \] Donc le cas de base est vérifié.
Étape inductive
Hypothèse d'induction : Supposons que la propriété est valable pour tous les u de longueur quelconque et tous les v de longueur \(k\) avec \(1 \le k \le n\).
Considérons maintenant un mot v de longueur \(n+1\). On peut l'écrire sous la forme \(v = wa\), où \(a \in \Sigma\) et \(w\) est un mot de longueur \(n\) (car en enlevant le dernier symbole, on obtient un mot de longueur \(n\)).
Alors :
- Par définition de la longueur : \(|v| = |w| + 1\)
- Par définition de la concaténation : \(uv = u(wa) = (uw)a\) (la concaténation est associative)
- Par définition de la longueur : \(|uv| = |(uw)a| = |uw| + 1\)
Par l'hypothèse d'induction (qui est applicable puisque w est de longueur n), nous avons : \[ |uw| = |u| + |w| \]
En substituant :
\[ |uv| = (|u| + |w|) + 1 = |u| + (|w| + 1) = |u| + |v| \]
Par conséquent, la propriété est valable pour tous les u et tous les v de longueur \(n+1\).
Conclusion
Par le principe d'induction, la propriété \(|uv| = |u| + |v|\) est vraie pour tous les mots u et v sur \(\Sigma\).
- Définition récursive de la longueur d'un mot
- Cas de base : \(v\) de longueur 1 (vérification directe)
- Hypothèse d'induction : propriété vraie pour tout mot v de longueur ≤ n
- Pas d'induction : pour un mot v de longueur n+1, on le décompose en \(v = wa\) et on utilise l'hypothèse sur w
- Conclusion : la propriété est vraie pour toute longueur
Exemple illustratif
Soit \(\Sigma = \{a, b\}\), \(u = aba\) et \(v = bba\).
- \(|u| = 3\) (a, b, a)
- \(|v| = 3\) (b, b, a)
- \(uv = ababba\)
- \(|uv| = 6\) (a, b, a, b, b, a)
On vérifie bien que \(|uv| = 6 = 3 + 3 = |u| + |v|\).
Cette démonstration est un exemple classique de récurrence structurelle : on utilise la définition récursive des mots pour prouver une propriété par induction sur la longueur. C'est une technique fondamentale en théorie des langages formels.
Résumé des étapes
| Étape | Description | Expression |
|---|---|---|
| Définition | Longueur d'un symbole | \(|a| = 1\) |
| Définition | Longueur d'un mot avec ajout | \(|wa| = |w| + 1\) |
| Cas base | v de longueur 1 | \(|ua| = |u| + 1 = |u| + |a|\) |
| Hypothèse | Propriété vraie pour |v| ≤ n | \(|uw| = |u| + |w|\) pour |w| = n |
| Pas inductif | v = wa avec |v| = n+1 | \(|uv| = |uwa| = |uw| + 1 = |u| + |w| + 1 = |u| + |v|\) |
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.