Voir la source de Mot (mathématiques)

{{homonyme|mot (homonymie)}}
En [[mathématiques]] ou en [[informatique théorique]], un '''mot''' est une [[Suite (mathématiques)|suite]] finie <math>w</math> d'éléments pris dans un ensemble <math>A</math>. L'ensemble <math>A</math> est appelé l'''alphabet'', ses éléments sont appelés ''symboles'' ou ''lettres''. On dit que <math>w</math> est un ''mot sur'' <math>A</math>.

En utilisant l'[[étoile de Kleene]], l'ensemble des mots sur <math>A</math> est noté <math>A^*</math>.

== Exemples ==

* Un « mot binaire ». C'est un mot sur un alphabet à deux symboles, notés généralement <math>0</math> et <math>1</math>. 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 <math>2</math>. Ainsi, l'écriture binaire de « dix-neuf » est <math>10011</math>.
* 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 <math>w= (a_1,a_2,\ldots, a_n)</math>
est écrit plus simplement : <math>w= a_1a_2\cdots a_n</math>

La '''longueur''' d'un mot est le nombre de positions des symboles qui le composent : le mot <math>w</math> ci-dessus est de longueur <math>n</math>.
Par exemple, le mot <math>abacaba</math> sur l'alphabet <math>A=\{a,b,c\}</math> 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 <math>u</math> et <math>v</math> est le mot <math>uv</math> obtenu en mettant bout à bout <math>u</math> et <math>v</math>. Par exemple, la concaténation de <math>u=abraca</math> et <math>v=dabra</math> donne <math>uv=abracadabra</math>. 
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 <math>A</math>, 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 <math>A</math> est traditionnellement noté <math>A^*</math>.

== Terminologie supplémentaire ==

* Les '''préfixes''' d'un mot  <math>w= a_1\cdots a_n</math> sont les <math>n+1</math> mots ε et <math>a_1\cdots a_i</math>, pour <math>i=1,\ldots,n</math>. <br>Les 5 préfixes du mot <math>abac</math> sont: ε, <math>a</math>, <math>ab</math>, <math>aba</math> et <math>abac</math> 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 <math>p</math> est un préfixe d'un mot <math>w</math> s'il existe un mot <math>s</math> tel que <math>w=ps</math>.

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

* Les '''facteurs''' d'un mot  <math>w= a_1\cdots a_n</math> sont les mots <math>a_i\cdots a_j</math>, pour <math>1\le i\le j\le n</math>. <br/>Les facteurs  du mot <math>abac</math> sont les mots ε, <math>a</math>, <math>b</math>, <math>c</math>, <math>ab</math>, <math>ba</math>, <math>ac</math>, <math>aba</math>, <math>bac</math>  et <math>abac </math>. De manière équivalente, un mot <math>x</math> est un facteur  d'un mot <math>w</math> s'il existe des mots <math>p,s</math> tel que <math>w=pxs</math>.

* Un mot <math>x</math> est un '''sous-mot''' d'un mot <math>y</math> s'il existe une factorisation <math>y=z_0x_1z_1x_2\cdots x_nz_n</math> en mots <math>z_0,x_1,z_1,x_2,\ldots, x_n,z_n</math> telle que <math>x=x_1x_2\cdots x_n</math>. <br/>Ainsi, <math>x</math> s'obtient à partir de <math>y</math> en effaçant des symboles dans <math>y</math>. Par exemple, <math>aa</math> est sous-mot de <math>abac</math><ref>Dans la littérature en langue anglaise, on dit ''{{Langue|en|subword}}'' pour ''facteur'' et ''{{Langue|en|scattered subword}}'' pour sous-mot.</ref>.

* L''''image miroir''' ou le '''retourné''' d'un mot <math>w= a_1\cdots a_n</math> est le mot <math>\tilde w= a_n\cdots a_1</math>. <br/>Par exemple, l'image miroir du mot <math>abac </math> est le mot <math>caba</math>.

* Un '''[[palindrome]]''' est un mot qui est égal à son image miroir. <br/> Par exemple, le mot  <math>abacaba </math> est un palindrome.

* Un mot <math>x</math> est '''puissance entière''' d'un mot <math>y</math> s'il existe un entier positif <math>n</math>  tel que <math>x=y^n</math> (<math>y</math> répété <math>n</math> fois).

* Un mot est '''[[mot primitif|primitif]]''' s'il n'est pas puissance entière d'un autre mot. <br/> Par exemple, le mot <math>bonbon</math> n'est pas primitif, parce qu'il est le carré du mot <math>bon</math>.

* Deux mots <math>x</math> et <math>y</math> sont '''conjugués''' s'il existe des mots <math>p</math> et <math>s</math> tels que <math>x=ps</math> et <math>y=sp</math>. Autrement dit, l’un des mots s’obtient depuis l’autre par une rotation de ses lettres. <br/>Par exemple, les mots <math>abaab</math> et <math>ababa</math> sont conjugués. La conjugaison est une [[relation d'équivalence]].

* Une '''classe de conjugaison''' ou '''mot circulaire'''  ou [[collier (combinatoire)|'''collier''']] est l'ensemble des conjugués d'un mot. Un mot circulaire de représentant <math>x</math> est parfois noté <math>(x)</math>. <br/> Par exemple, la classe de conjugaison de <math>abaab</math> est composée des cinq mots <math>abaab, baaba, aabab, ababa, babaa</math>.

* Une '''période''' d'un mot <math> x=a_1a_2\cdots a_n</math>, où <math> a_1,a_2,\ldots, a_n</math> sont des symboles, est un entier <math>p</math> avec <math> 1\le p\le n</math> tel que <math>a_i=a_{i+p}</math> pour <math> i=1,\ldots, n-p</math>. <br/>Par exemple, le mot <math>abaababa</math> 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 <math>uu</math> est périodique. Le mot <math>aababaabab = (aabab)^2</math> est périodique alors que le mot <math>abaababa</math> ne l'est pas.

* Un '''bord''' d'un mot <math>x</math> est un mot <math>y</math> qui est à la fois un préfixe propre et un suffixe propre de <math>x</math>. <br/>Par exemple, les bords du mot <math>abaababa</math> sont le mot vide, et <math>a, aba</math>. Si <math>y</math> est un bord d'un mot <math>x</math>, alors <math>|x|-|y|</math> est une période de <math>x</math>. 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''' <math>x</math> ш <math>y</math> de deux mots <math>x</math> et <math>y</math> est l'ensemble des mots <math>x_1y_1x_2y_2\cdots x_ny_n</math>, où les <math>x_i</math> et les <math>y_i</math>  sont des mots, tels que <math>x=x_1x_2\dots x_n</math> et <math>y=y_1y_2\dots y_n</math>. <br>Par exemple, <math>ab</math> ш <math>ab=\{aabb,abab\}</math><ref>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{ш}.
 </ref>{{,}}<ref>Pour bien comprendre cet exemple, écrivons en majuscules les lettres du deuxième mot. Avec cette convention, on a
:<math>ab</math> ш <math>AB=\{abAB,aAbB,AabB,aABb,AaBb,ABab\}</math>
et quand on revient aux minuscules, il ne reste plus que les deux mots indiqués. </ref>.

* 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 <math>x\le y</math> si et seulement si <math>x</math> est préfixe de <math>y</math> ou si <math>x=zax'</math>, et <math>y=zby'</math> pour des mots <math>z,x',y'</math> et des symboles <math>a</math> et <math>b</math> avec <math>a < b</math>. Par exemple, pour l'alphabet formé de <math>0</math> et <math>1</math> avec <math>0<1</math>, on a <math>\varepsilon<0<00<000<01<1<10\cdots</math>.
{{article détaillé|ordre lexicographique}}

== Lemme de Levi ==
{{article détaillé|Lemme de Levi}}
{{Théorème|Lemme de [[Friedrich Wilhelm Levi|Levi]]<ref name="Levi"/>|Soient <math>x</math>, <math>y</math>, <math>x'</math>, <math>y'</math> des mots. Si <math>xy=x'y'</math>, alors il existe un mot <math>z</math> tel que <math>x=x'z</math>, <math>y'=zy</math> ou <math>x'=xz</math>, <math>y=zy'</math>.}}

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

== Un résultat fondamental ==

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

{{théorème|
Soient <math>x</math> et <math>y</math> deux mots non vides. Les conditions suivantes sont équivalentes:
* <math>xy=yx</math>,
* il existe deux entiers <math> n,m\ge1</math> tels que <math>x^n=y^m</math>,
* il existe un mot <math>z</math> et deux entiers <math> p,q\ge1</math> tels que <math>x=z^p</math> et <math>y=z^q</math>.}}

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

Le théorème admet une version plus forte: 
{{énoncé|Si <math>x</math> et <math>y</math> sont deux mots non vides, et s'il existe une relation quelconque, non triviale, entre <math>x</math> et <math>y</math>, c'est-à-dire s'il existe une relation
:<math>z_1z_2\cdots z_n=z'_1z'_2\cdots z'_m</math>
où <math>z_1,z_2,\ldots, z_n,z'_1,z'_2,\ldots,z'_m</math> sont soit <math>x</math> ou  <math>y</math> et 
<math>z_1\ne z'_1</math>, alors <math>xy=yx</math>.}}

On peut exprimer ces résultats sous forme d'[[équation entre mots|équations entre mots]] : le premier dit que l'équation
:<math>XY=YX</math> 
en les inconnues <math>X, Y</math> 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 <math>x, y, z</math> des mots non vides. Alors 
:<math>xy = yz</math> 
si et seulement s'il existe un mot non vide <math>u</math>, un mot <math>v</math> et un entier <math>e\ge0</math> tels que 
:<math>x=uv, z=vu</math>, et <math>y= (uv)^eu=u(vu)^e</math>.
}}
Ce résultat est parfois attribué à [[Roger C. Lyndon|Lyndon]] et [[Marcel-Paul Schützenberger|Schützenberger]]<ref>Par exemple dans le manuel de {{harvsp|Shallit|2009|loc=2.3 The theorems of Lyndon–Schützenberger}}.</ref>. On peut voir cet énoncé comme la description des solutions de l'équation 
:<math>XY=YZ</math>
en trois variables <math>X,Y,Z</math>.

== Morphisme ==
{{loupe|contenu=Voir aussi : [[Monoïde#Morphisme de monoïdes|Morphisme de monoïdes]] et [[Morphisme#Cas des monoïdes|Cas des morphismes de monoïdes]].}}
Une application 
:<math>h: A^*\to B^*</math> 
est un '''morphisme''' ou un ''homomorphisme'' si elle vérifie 
:<math>h(xy)=h(x)h(y)</math>
pour tous les mots <math>x,y\in A^*</math>. Tout morphisme est déterminé par sa donnée sur les lettres de l'alphabet <math>A</math>. En effet, pour un mot <math>w= a_1a_2\cdots a_n</math>, on a
:<math>h(w)= h(a_1)h(a_2)\cdots h(a_n)</math>.
De plus, l'image du mot vide est le mot vide : 
:<math>h(\varepsilon)=\varepsilon</math> 
parce que <math>\varepsilon</math> est le seul mot égal à son carré, et 
:<math>h(\varepsilon)=h(\varepsilon\varepsilon)=h(\varepsilon)h(\varepsilon)</math>. 

=== Exemples ===
{{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 
<math>\mu: A^*\to A^*</math> sur <math>A=\{0,1\}</math> défini par
:<math>\mu(0)=01</math>
:<math>\mu(1)=10</math>
En itérant, on obtient
:<math>\mu(01)=0110</math>
:<math>\mu(0110)=01101001</math>
:<math>\mu(01101001)=0110100110010110</math>

{{article détaillé|mot de Fibonacci}}
Le '''morphisme de Fibonacci''' permet de définir le [[mot de Fibonacci]]. C'est le morphisme 
<math>\phi: A^*\to A^*</math>, avec <math>A=\{a,b\}</math>, défini par
:<math>\phi(a)=ab</math>
:<math>\phi(b)=a</math>
En itérant, on obtient
:<math>\phi(ab)=aba</math>
:<math>\phi(aba)=abaab</math>
:<math>\phi(abaab)=abaababa</math>

=== Morphismes particuliers ===
* Un automorphisme <math>h:A^*\to A^*</math> est une bijection si et seulement l'image d'un symbole est un symbole.
* Un morphisme <math>h</math> 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 : <math>|h(w)|\ge|w|</math>. On dit aussi morphisme ''non décroissant'', ou ''croissant au sens large''. On dit aussi que c'est un [[Demi-groupe#Morphisme|morphisme de demi-groupes]] puisque sa restriction au demi-groupe <math>A^+=A^*\setminus\varepsilon</math> est à valeurs dans <math>B^+</math>.
* 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 <math>h</math> est '''uniforme''' si les images des symboles ont toutes la même longueur. Si la longueur commune est <math>k</math>, ont dit aussi que le morphisme est <math>k</math>-''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 <math>h:A^*\to A^*</math> est '''symétrique'''<ref>Cette terminologie est employée par {{Article|langue=en |prénom1=Anna E.|nom1=Frid| titre=Arithmetical complexity of the symmetric D0L words |périodique=Theoretical Computer Science |année=2003 |volume=306 |pages=535-542}}.</ref> s'il existe une permutation ''circulaire'' <math>s:A\to A</math> de l'alphabet qui commute avec <math>h</math>, c'est-à-dire telle que {{indente|<math>h(s(a))=s(h(a))</math>}} pour tout symbole <math>a</math>. Ici <math>s</math> est étendu en un automorphisme de <math>A^*</math>. Cette formule implique que <math>h</math> 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 ===
{{Références|colonnes=2|références= 
<ref name="Levi">Cet énoncé est en fait la partie facile. Il y a une réciproque: si un monoïde <math>M</math> vérifie la conclusion du lemme, et si de plus il existe un morphisme <math>\lambda</math> de <math>M</math> dans le monoïde additif des entiers naturels tel que <math>\lambda^{-1}(0)=1</math>, alors M est libre (voir Lothaire (1983), Problème 1.1.1).</ref>
}}

=== Articles connexes ===
* [[Formule (mathématiques)]]
* [[Combinatoire des mots]]
* [[Concaténation]]
* [[Théorie des langages]]

=== Bibliographie ===
<!-- Par ordre alphabétique -->
* {{Ouvrage
 | auteur1=Jean-Michel Autebert
 | titre=Langages algébriques
 | éditeur=Masson
 | année=1987
 | pages totales=278
 | isbn=978-2-225-81087-9
 | id=Autebert
}}  
* {{Ouvrage
 | langue=fr
 | auteur1=Olivier Carton
 | titre=Langages formels, calculabilité et complexité
 | sous-titre=licence et master de mathématiques ou d'informatique, option informatique de l'agrégation de mathématiques
 | lieu=Paris
 | éditeur=[[Vuibert]]
 | année=2008
 | pages totales=237
 | isbn=978-2-7117-2077-4
 | id=Carton2008
}}  
* {{Ouvrage
 | langue=fr
 | auteur1=[[Maxime Crochemore]]
 | auteur2=Christophe Hancart
 | auteur3=Thierry Lecroq
 | titre=Algorithmique du texte
 | lieu=Paris
 | éditeur=[[Vuibert]]
 | année=2004
 | pages totales=347
 | isbn=2-7117-8628-5
 | id=AdT
}}  
* {{Ouvrage | langue=en | auteur1=M. Lothaire | titre=Combinatorics on Words | volume=17 | éditeur=Addison-Wesley Publishing Co., Reading, Mass. | série=Encyclopedia of Mathematics and its Applications | année=1983 | pages totales=238 | isbn=978-0-201-13516-9 | présentation en ligne={{Google Livres|id=UV9_3plEr8wC}}}} — Une seconde édition, révisée, est parue chez [[Cambridge University Press]], dans la collection Cambridge Mathematical Library, en 1997, {{ISBN|978-0521599245}}.
* {{Ouvrage | langue=en | auteur1=Jeffrey Shallit | titre=A Second Course in Formal Languages and Automata Theory | éditeur=[[Cambridge University Press]] | année=2009 | pages totales=240 | isbn=978-0-521-86572-2}}

{{Portail|mathématiques| informatique théorique}}

[[Catégorie:Mathématiques discrètes]]
[[Catégorie:Combinatoire des mots]]