Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] \| Liste Catégories \| Une page au hasard \| Pages liées

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 et , où m et n sont des entiers naturels, associe la séquence .
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 et d'un mot de .
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.

Catégories: Langages formels | Programmation informatique

This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the