Mot (mathématiques)

• Un « mot binaire ». C'est un mot sur un alphabet à deux symboles, notés généralement ${\displaystyle 0}$ et ${\displaystyle 1}$. Par exemple, le développement binaire d'un entier naturel, ou son écriture binaire, est la suite des chiffres de sa représentation en base ${\displaystyle 2}$. Ainsi, l'écriture binaire de « dix-neuf » est ${\displaystyle 10011}$.
• Une « séquence d'acide désoxyribonucléique » (ADN). C'est un mot généralement formé d'une suite de quatre lettres correspondant aux quatre nucléotides formant l'enchaînement de l'ADN : A pour « adénine », G pour « guanine », T pour « thymine », C pour « cytosine ».
• Une « protéine » est une macromolécule composée d’une chaîne d'acides aminés. Il y a 20 acides aminés. C'est donc un mot sur un alphabet de 20 symboles.

Un mot ${\displaystyle w=(a_{1},a_{2},\ldots ,a_{n})}$ est écrit plus simplement : ${\displaystyle w=a_{1}a_{2}\cdots a_{n}}$

La longueur d'un mot est le nombre de positions des symboles qui le composent : le mot ${\displaystyle w}$ ci-dessus est de longueur ${\displaystyle n}$. Par exemple, le mot ${\displaystyle abacaba}$ sur l'alphabet ${\displaystyle A=\{a,b,c\}}$ est de longueur 7. Un mot peut être vide. C'est le mot de longueur 0. Il est fréquemment noté ε.

La concaténation de deux mots ${\displaystyle u}$ et ${\displaystyle v}$ est le mot ${\displaystyle uv}$ obtenu en mettant bout à bout ${\displaystyle u}$ et ${\displaystyle v}$. Par exemple, la concaténation de ${\displaystyle u=abraca}$ et ${\displaystyle v=dabra}$ donne ${\displaystyle uv=abracadabra}$. La concaténation est une opération associative, mais non commutative. Son élément neutre est le mot vide.

L'ensemble des mots sur un alphabet ${\displaystyle A}$, muni de la concaténation, forme donc un monoïde. En tant que structure algébrique, c'est un monoïde libre au sens de l'algèbre universelle. Cela signifie que tout mot est produit de concaténation des symboles qui le composent.

L'ensemble des mots sur un alphabet ${\displaystyle A}$ est traditionnellement noté ${\displaystyle A^{*}}$.

• Les préfixes d'un mot ${\displaystyle w=a_{1}\cdots a_{n}}$ sont les ${\displaystyle n+1}$ mots ε et ${\displaystyle a_{1}\cdots a_{i}}$, pour ${\displaystyle i=1,\ldots ,n}$.
  Les 5 préfixes du mot ${\displaystyle abac}$ sont: ε, ${\displaystyle a}$, ${\displaystyle ab}$, ${\displaystyle aba}$ et ${\displaystyle abac}$ lui-même. Si on exclut le mot vide, on parle de préfixe non vide, si on exclut le mot lui-même, on parle de préfixe propre. De manière équivalente, un mot ${\displaystyle p}$ est un préfixe d'un mot ${\displaystyle w}$ s'il existe un mot ${\displaystyle s}$ tel que ${\displaystyle w=ps}$.

• Les suffixes d'un mot ${\displaystyle w=a_{1}\cdots a_{n}}$ sont les ${\displaystyle n+1}$ mots ε et ${\displaystyle a_{i}\cdots a_{n}}$, pour ${\displaystyle i=1,\ldots ,n}$.
  Les 5 suffixes du mot ${\displaystyle abac}$ sont: les mots ${\displaystyle abac}$, ${\displaystyle bac}$, ${\displaystyle ac}$, ${\displaystyle c}$ et ε. De manière équivalente, un mot ${\displaystyle s}$ est un suffixe d'un mot ${\displaystyle w}$ s'il existe un mot ${\displaystyle p}$ tel que ${\displaystyle w=ps}$.

• Les facteurs d'un mot ${\displaystyle w=a_{1}\cdots a_{n}}$ sont les mots ${\displaystyle a_{i}\cdots a_{j}}$, pour ${\displaystyle 1\leq i\leq j\leq n}$.
  Les facteurs du mot ${\displaystyle abac}$ sont les mots ε, ${\displaystyle a}$, ${\displaystyle b}$, ${\displaystyle c}$, ${\displaystyle ab}$, ${\displaystyle ba}$, ${\displaystyle ac}$, ${\displaystyle aba}$, ${\displaystyle bac}$ et ${\displaystyle abac}$. De manière équivalente, un mot ${\displaystyle x}$ est un facteur d'un mot ${\displaystyle w}$ s'il existe des mots ${\displaystyle p,s}$ tel que ${\displaystyle w=pxs}$.

• Un mot ${\displaystyle x}$ est un sous-mot d'un mot ${\displaystyle y}$ s'il existe une factorisation ${\displaystyle y=z_{0}x_{1}z_{1}x_{2}\cdots x_{n}z_{n}}$ en mots ${\displaystyle z_{0},x_{1},z_{1},x_{2},\ldots ,x_{n},z_{n}}$ telle que ${\displaystyle x=x_{1}x_{2}\cdots x_{n}}$.
  Ainsi, ${\displaystyle x}$ s'obtient à partir de ${\displaystyle y}$ en effaçant des symboles dans ${\displaystyle y}$. Par exemple, ${\displaystyle aa}$ est sous-mot de ${\displaystyle abac}$[1].

• L'image miroir ou le retourné d'un mot ${\displaystyle w=a_{1}\cdots a_{n}}$ est le mot ${\displaystyle {\tilde {w}}=a_{n}\cdots a_{1}}$.
  Par exemple, l'image miroir du mot ${\displaystyle abac}$ est le mot ${\displaystyle caba}$.

• Un palindrome est un mot qui est égal à son image miroir.
  Par exemple, le mot ${\displaystyle abacaba}$ est un palindrome.

• Un mot ${\displaystyle x}$ est puissance entière d'un mot ${\displaystyle y}$ s'il existe un entier positif ${\displaystyle n}$ tel que ${\displaystyle x=y^{n}}$ (${\displaystyle y}$ répété ${\displaystyle n}$ fois).

• Un mot est primitif s'il n'est pas puissance entière d'un autre mot.
  Par exemple, le mot ${\displaystyle bonbon}$ n'est pas primitif, parce qu'il est le carré du mot ${\displaystyle bon}$.

• Deux mots ${\displaystyle x}$ et ${\displaystyle y}$ sont conjugués s'il existe des mots ${\displaystyle p}$ et ${\displaystyle s}$ tels que ${\displaystyle x=ps}$ et ${\displaystyle y=sp}$.
  Par exemple, les mots ${\displaystyle abaab}$ et ${\displaystyle ababa}$ sont conjugués. La conjugaison est une relation d'équivalence.

• Une classe de conjugaison ou mot circulaire ou collier est l'ensemble des conjugués d'un mot.
  Un mot circulaire de représentant ${\displaystyle x}$ est parfois noté ${\displaystyle (x)}$. Par exemple, la classe de conjugaison de ${\displaystyle abaab}$ est composée des cinq mots ${\displaystyle abaab,baaba,aabab,ababa,babaa}$.

• Une période d'un mot ${\displaystyle x=a_{1}a_{2}\cdots a_{n}}$, où ${\displaystyle a_{1},a_{2},\ldots ,a_{n}}$ sont des symboles, est un entier ${\displaystyle p}$ avec ${\displaystyle 1\leq p\leq n}$ tel que ${\displaystyle a_{i}=a_{i+p}}$ pour ${\displaystyle i=1,\ldots ,n-p}$.
  Par exemple, le mot ${\displaystyle abaababa}$ a les périodes 5, 7 et 8.

• Un mot périodique est un mot dont la longueur est au moins deux fois sa période minimale. Un carré, c'est-à-dire un mot de la forme ${\displaystyle uu}$ est périodique. Le mot ${\displaystyle aababaababa=(aababa)^{2}a}$ est périodique alors que le mot ${\displaystyle abaababa}$ ne l'est pas.

• Un bord d'un mot ${\displaystyle x}$ est un mot ${\displaystyle y}$ qui est à la fois un préfixe propre et un suffixe propre de ${\displaystyle x}$.
  Par exemple, les bords du mot ${\displaystyle abaababa}$ sont le mot vide, et ${\displaystyle a,aba}$. Si ${\displaystyle y}$ est un bord d'un mot ${\displaystyle x}$, alors ${\displaystyle |x|-|y|}$ est une période de ${\displaystyle x}$. Un mot sans bord est un mot dont le seul bord est le mot vide. C'est un mot dont la seule période est sa longueur.

• Le produit de mélange ${\displaystyle x}$ ш ${\displaystyle y}$ de deux mots ${\displaystyle x}$ et ${\displaystyle y}$ est l'ensemble des mots ${\displaystyle x_{1}y_{1}x_{2}y_{2}\cdots x_{n}y_{n}}$, où les ${\displaystyle x_{i}}$ et les ${\displaystyle y_{i}}$ sont des mots, tels que ${\displaystyle x=x_{1}x_{2}\dots x_{n}}$ et ${\displaystyle y=y_{1}y_{2}\dots y_{n}}$.
  Par exemple, ${\displaystyle ab}$ ш ${\displaystyle ab=\{aabb,abab\}}$[2]^,[3].

• L'ordre lexicographique sur les mots se définit à partir d'un ordre total sur l'alphabet. C'est l'ordre alphabétique, formellement donné par ${\displaystyle x\leq y}$ si et seulement si ${\displaystyle x}$ est préfixe de ${\displaystyle y}$ ou si ${\displaystyle x=zax'}$, et ${\displaystyle y=zby'}$ pour des mots ${\displaystyle z,x',y'}$ et des symboles ${\displaystyle a}$ et ${\displaystyle b}$ avec ${\displaystyle a<b}$. Par exemple, pour l'alphabet formé de ${\displaystyle 0}$ et ${\displaystyle 1}$ avec ${\displaystyle 0<1}$, on a ${\displaystyle \varepsilon <0<00<000<01<1<10\cdots }$.

Une autre façon d'exprimer ce résultat est de dire que si ${\displaystyle x}$ et ${\displaystyle x'}$ sont tous les deux des préfixes d'un mot, alors ${\displaystyle x}$ est préfixe de ${\displaystyle x'}$ ou ${\displaystyle x'}$ est préfixe de ${\displaystyle x}$.

Le résultat suivant caractérise les mots qui commutent.

Parmi les conséquences, il y a :

• Tout mot est puissance d'un mot primitif unique.
• Les conjugués d'un mot primitif sont eux-mêmes primitifs.
• La classe de conjugaison d'un mot primitif de longueur ${\displaystyle n}$ a ${\displaystyle n}$ éléments.

Le théorème admet une version plus forte:

Si ${\displaystyle x}$ et ${\displaystyle y}$ sont deux mots non vides, et s'il existe une relation quelconque, non triviale, entre ${\displaystyle x}$ et ${\displaystyle y}$, c'est-à-dire s'il existe une relation

${\displaystyle z_{1}z_{2}\cdots z_{n}=z'_{1}z'_{2}\cdots z'_{m}}$

où ${\displaystyle z_{1},z_{2},\ldots ,z_{n},z'_{1},z'_{2},\ldots ,z'_{m}}$ sont soit ${\displaystyle x}$ ou ${\displaystyle y}$ et

${\displaystyle z_{1}\neq z'_{1}}$, alors ${\displaystyle xy=yx}$.

On peut exprimer ces résultats sous forme d'équations entre mots : le premier dit que l'équation

${\displaystyle XY=YX}$

en les inconnues ${\displaystyle X,Y}$ n'a que des solutions cycliques, c'est-à-dire dont tous les mots sont des puissances d'un même mot ; le deuxième dit que toute équation en deux variables sans constante n'a que des solutions cycliques.

Une autre propriété concerne la conjugaison.

Ce résultat est parfois attribué à Lyndon et Schützenberger[5]. On peut voir cet énoncé comme la description des solutions de l'équation

${\displaystyle XY=YZ}$

en trois variables ${\displaystyle X,Y,Z}$.

Une application

${\displaystyle h:A^{*}\to B^{*}}$

est un morphisme ou un homomorphisme si elle vérifie

${\displaystyle h(xy)=h(x)h(y)}$

pour tous les mots ${\displaystyle x,y\in A^{*}}$. Tout morphisme est déterminé par sa donnée sur les lettres de l'alphabet ${\displaystyle A}$. En effet, pour un mot ${\displaystyle w=a_{1}a_{2}\cdots a_{n}}$, on a

${\displaystyle h(w)=h(a_{1})h(a_{2})\cdots h(a_{n})}$.

De plus, l'image du mot vide est le mot vide :

${\displaystyle h(\varepsilon )=\varepsilon }$

parce que ${\displaystyle \varepsilon }$ est le seul mot égal à son carré, et

${\displaystyle h(\varepsilon )=h(\varepsilon \varepsilon )=h(\varepsilon )h(\varepsilon )}$.

Un polynôme non commutatif est une combinaison linéaire de mots sur une famille d’indéterminées.