Concaténation

Informellement, en programmation, on appelle la concaténation de deux chaînes de caractères, la chaîne formée de ces deux chaînes mises bout à bout.

Exemple :

La concaténation de « Hello » et « world! » est « Hello world! »

Plus formellement, dans le contexte théorique des langages formels : Si on se donne un ensemble fini Σ, et que l'on appelle $\Sigma^\star$ l'ensemble des séquences d'éléments de Σ, la concaténation est la loi de composition interne sur $\Sigma^\star$ qui aux séquences $(a 1, a 2 ... a m)$ et $(b 1, b 2 ... b n)$ , où m et n sont des entiers naturels, associe la séquence $(a 1, a 2 ... a m, b 1, b 2 ... b n)$ .
Cette opération est associative et a un élément neutre qui est la séquence vide, donc elle dote $\Sigma^\star$ d'une structure algébrique de monoïde. De plus, ce monoïde, ainsi que tous les monoïdes isomorphes à celui-ci est qualifié de libre (la définition de monoïde libre découle de celle de concaténation).

En généralisant, on introduira la terminologie suivante : Si on se donne un monoïde libre, on appelera concaténation (notée souvent par un point $\cdot$ , ou par rien) sa loi de composition interne, mot vide (noté ε) son élément neutre, mots ou chaînes de caractères ses éléments, alphabet (noté A ou Σ) son ensemble de générateurs libres, symboles, lettres ou caractères les éléments de l'alphabet. Dans cette terminologie, on appellera ce monoïde le langage des mots sur l'alphabet Σ (ou A ...), que l'on notera $\Sigma^\star$ (ou $A^\star$ ).

La concaténation est une opération sur les mots, mais peut être étendue aux langages (sous-ensembles du monoïde). Ainsi, si $L_1, L_2 \in \Sigma^\star$ alors leur concaténation $L_1\cdot L_2$ est l'ensemble $\{v\cdot w | (v,w)\in L_1\times L_2\}$ , c'est-à-dire l'ensemble des mots qui sont la concaténation d'un mot de $L 1$ et d'un mot de $L 2$ .
Cette extension de la concaténation est l'une des trois opérations de base permettant de construire des langages réguliers, c'est-à-dire un des trois opérateurs de base que l'on peut rencontrer dans une expression régulière. Les deux autres opérations sont l'union ensembliste et la fermeture de Kleene.

Concaténation

See also: Concaténation, Alphabet, Chaîne de caractères, Expression régulière, Fermeture de Kleene, Langage formel, Langage régulier, Loi de composition interne, Monoïde, Opération ensembliste