Mot (mathématiques)

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 appelés symboles ou lettres. On dit que est un mot sur .

En utilisant l'étoile de Kleene, l'ensemble des mots sur est noté .

Exemples

  • 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é 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.

Propriétés

Un mot est écrit plus simplement :

La longueur d'un mot est le nombre de positions des symboles 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 fréquemment noté ε.

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 symboles qui le composent.

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

Terminologie supplémentaire

  • 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 symboles 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 .
  • Deux mots et sont conjugués s'il existe des mots et tels que et . Autrement dit, l’un des mots s’obtient depuis l’autre par une rotation de ses lettres.
    Par exemple, les mots et 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 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 symboles, 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 symboles et avec . Par exemple, pour l'alphabet formé de et avec , on a .

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 fondamental

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 sous forme d'équations entre mots : le premier dit que l'équation

en les inconnues 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 .

Morphisme

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

.

Exemples

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

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 particuliers

  • Un automorphisme est une bijection si et seulement l'image d'un symbole est un symbole.
  • Un morphisme est non effaçant si l'image d'un symbole 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'un symbole est un symbole 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 symbole est un symbole. Il est équivalent de dire que l'image d'un mot est de même longueur que le mot de départ.
  • Un morphisme est uniforme si les images des symboles 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 tout symbole . Ici est étendu en un automorphisme de . Cette formule implique que est uniforme. Le morphisme de Thue-Morse est symétrique.

Applications

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

Notes et références

Références

  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 connexes

Bibliographie

  • Jean-Michel Autebert, Langages algébriques, Masson, , 278 p. (ISBN 978-2-225-81087-9)
  • Olivier Carton, Langages formels, calculabilité et complexité : licence et master de mathématiques ou d'informatique, option informatique de l'agrégation de mathématiques, Paris, Vuibert, , 237 p. (ISBN 978-2-7117-2077-4)
  • Maxime Crochemore, Christophe Hancart et Thierry Lecroq, Algorithmique du texte, Paris, Vuibert, , 347 p. (ISBN 2-7117-8628-5)
  • (en) M. Lothaire, Combinatorics on Words, vol. 17, Addison-Wesley Publishing Co., Reading, Mass., , 238 p. (ISBN 978-0-201-13516-9, présentation en ligne) — Une seconde édition, révisée, est parue chez Cambridge University Press, dans la collection Cambridge Mathematical Library, en 1997, (ISBN 978-0521599245).
  • (en) Jeffrey Shallit, A Second Course in Formal Languages and Automata Theory, Cambridge University Press, , 240 p. (ISBN 978-0-521-86572-2)