Ouvrir le menu principal
Page d'aide sur l'homonymie Pour les articles homonymes, voir mot (homonymie).

En mathématiques ou en informatique théorique, un mot est une suite finie d'éléments pris dans un ensemble . L'ensemble est appelé l'alphabet, ses éléments sont des lettres. On dit que est un mot sur .

Sommaire

ExemplesModifier

  • Un « mot binaire ». C'est un mot sur un alphabet à deux symboles, notés généralement   et  . 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  . Ainsi, l'écriture binaire de « dix-neuf » est  .
  • Une « séquence d'acide désoxyribonucléique » (ADN). C'est un mot généralement formé 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. Lorsqu'à une position donnée, il y a incertitude sur le nucléotide, un N est utilisé au lieu de A, G, T ou C.
  • 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 à 20 lettres.
  • La transmission des textes est facilitée par l'emploi d'un alphabet appelé unicode. C'est une norme qui vise à donner à tout caractère de n’importe quel système d’écriture un nom et un identifiant numérique.

PropriétésModifier

Un mot   est écrit plus simplement :  

La longueur d'un mot est le nombre de positions des lettres qui le composent : le mot   ci-dessus est de longueur  . Par exemple, le mot   sur l'alphabet   est de longueur 7. Un mot peut être vide. C'est le mot de longueur 0. Il est noté généralement ε.

La concaténation de deux mots   et   est le mot   obtenu en mettant bout à bout   et  . Par exemple, la concaténation de   et   donne  . 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  , 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 lettres qui le composent.

L'ensemble des mots sur un alphabet   est traditionnellement noté  .

Terminologie supplémentaireModifier

  • Les préfixes d'un mot   sont les   mots ε et  , pour  .
    Les 5 préfixes du mot   sont: ε,  ,  ,   et   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   est un préfixe d'un mot   s'il existe un mot   tel que  .
  • Les suffixes d'un mot   sont les   mots ε et  , pour  .
    Les 5 suffixes du mot   sont: les mots  ,  ,  ,   et ε. De manière équivalente, un mot   est un suffixe d'un mot   s'il existe un mot   tel que  .
  • Les facteurs d'un mot   sont les mots  , pour  .
    Les facteurs du mot   sont les mots ε,  ,  ,  ,  ,  ,  ,  ,   et  . De manière équivalente, un mot   est un facteur d'un mot   s'il existe des mots   tel que  .
  • Un mot   est un sous-mot d'un mot   s'il existe une factorisation   en mots   telle que  .
    Ainsi,   s'obtient à partir de   en effaçant des lettres dans  . Par exemple,   est sous-mot de  [1].
  • L'image miroir ou le retourné d'un mot   est le mot  .
    Par exemple, l'image miroir du mot   est le mot  .
  • Un palindrome est un mot qui est égal à son image miroir.
    Par exemple, le mot   est un palindrome.
  • Un mot   est puissance entière d'un mot   s'il existe un entier positif   tel que   (  répété   fois).
  • Un mot est primitif s'il n'est pas puissance entière d'un autre mot.
    Par exemple, le mot   n'est pas primitif, parce qu'il est le carré du mot  .
Article détaillé : mot primitif.
  • Deux mots   et   sont conjugués s'il existe des mots   et   tels que   et  .
    Par exemple, les mots   et   sont conjugués. La conjugaison est une relation d'équivalence.
  • Un classe de conjugaison ou mot circulaire ou collier est l'ensemble des conjugués d'un mot.
    Un mot circulaire de représentant   est parfois noté  . Par exemple, la classe de conjugaison de   est composée des cinq mots  .
  • Une période d'un mot  , où   sont des lettres, est un entier   avec   tel que   pour  .
    Par exemple, le mot   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   est périodique. Le mot   est périodique alors que le mot   ne l'est pas.
  • Un bord d'un mot   est un mot   qui est à la fois un préfixe propre et un suffixe propre de  .
    Par exemple, les bords du mot   sont le mot vide, et  . Si   est un bord d'un mot  , alors   est une période de  . 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   ш   de deux mots   et   est l'ensemble des mots  , où les   et les   sont des mots, tels que   et  .
    Par exemple,   ш  [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   si et seulement si   est préfixe de   ou si  , et   pour des mots   et des lettres   et   avec  . Par exemple, pour l'alphabet formé de   et   avec  , on a  .
Article détaillé : ordre lexicographique.

Lemme de LeviModifier

Article détaillé : Lemme de Levi.

lemme de Levi[4] — Soient  ,  ,  ,   des mots. Si  , alors il existe un mot   tel que  ,   ou  ,  .

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

Un résultat fondamentalModifier

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

Théorème —  Soient   et   deux mots non vides. Les conditions suivantes sont équivalentes:

  •  ,
  • il existe deux entiers   tels que  ,
  • il existe un mot   et deux entiers   tels que   et  .

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   a   éléments.

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

Si   et   sont deux mots non vides, et s'il existe une relation quelconque, non triviale, entre   et  , c'est-à-dire s'il existe une relation

 

  sont soit   ou   et

 , alors  .

On peut exprimer ces résultats en terme d'équation entre mots : le premier dit que l'équation

 

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.

Théorème — Soient   des mots non vides. Alors

 

si et seulement s'il existe un mot non vide  , un mot   et un entier   tels que

 , et  .

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

 .

MorphismeModifier

Une application

 

est un morphisme ou un homomorphisme si elle vérifie

 

pour tous les mots  . Tout morphisme est déterminé par sa donnée sur les lettres de l'alphabet  . En effet, pour un mot  , on a

 .

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

 

parce que   est le seul mot égal à son carré, et

 .

ExemplesModifier

Article détaillé : suite de Prouhet-Thue-Morse.

Le morphisme de Thue-Morse permet de définir la suite de Prouhet-Thue-Morse. C'est le morphisme   sur   défini par

 
 

En itérant, on obtient

 
 
 
Article détaillé : mot de Fibonacci.

Le morphisme de Fibonacci permet de définir le mot de Fibonacci. C'est le morphisme  , avec  , défini par

 
 

En itérant, on obtient

 
 
 

Morphismes particuliersModifier

  • Un automorphisme   est une bijection si et seulement l'image d'une lettre est une lettre.
  • Un morphisme   est non effaçant si l'image d'une lettre n'est jamais le mot vide. Il est équivalent de dire que l'image d'un mot est toujours au moins aussi longue que le mot de départ :  . On dit aussi morphisme non décroissant, ou croissant au sens large. On dit aussi que c'est un morphisme de demi-groupes puisque sa restriction au demi-groupe   est à valeurs dans  .
  • Un morphisme est alphabétique si l'image d'une lettre est une lettre ou le mot vide. Il est équivalent de dire que l'image d'un mot est toujours moins longue que le mot de départ.
  • Un morphisme est littéral ou lettre à lettre ou préserve la longueur si l'image d'une lettre est une lettre. Il est équivalent de dire que l'image d'un mot est toujours moins longue que le mot de départ.
  • Un morphisme   est uniforme si les images des lettres ont toutes la même longueur. Si la longueur commune est  , ont dit aussi que le morphisme est  -uniforme. Le morphisme de Thue-Morse est 2-uniforme; le morphisme de Fibonacci est non effaçant, et n'est pas uniforme. Un morphisme littéral est 1-uniforme.
  • Un morphisme   est symétrique[6] s'il existe une permutation circulaire   de l'alphabet qui commute avec  , c'est-à-dire telle que   pour toute lettre  . Ici   est étendu en un automorphisme de  . Cette formule implique que   est uniforme. Le morphisme de Thue-Morse est symétrique.

Notes et référencesModifier

RéférencesModifier

  1. Dans la littérature en langue anglaise, on dit subword pour facteur et scattered subword pour sous-mot.
  2. Le symbole « ш » est la lettre sha de l'alphabet cyrillique, On utilise aussi le caractère unicode U+29E2 (SHUFFLE PRODUCT)). Dans une formule mathématique, on peut aussi utiliser \text{ш}.
  3. Pour bien comprendre cet exemple, écrivons en majuscules les lettres du deuxième mot. Avec cette convention, on a
      ш  
    et quand on revient aux minuscules, il ne reste plus que les deux mots indiqués.
  4. Cet énoncé est en fait la partie facile. Il y a une réciproque: si un monoïde   vérifie la conclusion du lemme, et si de plus il existe un morphisme   de   dans le monoïde additif des entiers naturels tel que  , alors M est libre (voir Lothaire (1983), Problème 1.1.1).
  5. Par exemple dans le manuel de Shallit 2009, 2.3 The theorems of Lyndon–Schützenberger.
  6. Cette terminologie est employée par (en) Anna E. Frid, « Arithmetical complexity of the symmetric D0L words », Theoretical Computer Science, vol. 306,‎ , p. 535-542.

Articles connexesModifier

BibliographieModifier