Mot (mathématiques)

Mot (mathématiques)
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 w d'éléments pris dans un ensemble A. L'ensemble A est appelé l'alphabet, ses éléments sont des lettres. On dit que w est un mot sur A.

Sommaire

Exemples

  • Un « mot binaire ». C'est un mot sur un alphabet à deux symboles, notés généralement 0 et 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 2. Ainsi, l'écriture binaire de « dix-neuf » est 10011.
  • 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és

Un mot w= (a_1,a_2,\ldots, a_n) est écrit plus simplement : w= a_1a_2\cdots a_n

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

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

Terminologie supplémentaire

  • Les préfixes d'un mot w= a_1\cdots a_n sont les n + 1 mots ε et a_1\cdots a_i, pour i=1,\ldots,n.

Les 5 préfixes du mot abac sont: ε, a, ab, aba et 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 p est un préfixe d'un mot w s'il existe un mot s tel que w = ps.

  • Les suffixes d'un mot w= a_1\cdots a_n sont les n + 1 mots ε et a_{i}\cdots a_n, pour i=1,\ldots,n.

Les 5 suffixes du mot abac sont: les mots abac, bac, ac, c et ε.

De manière équivalente, un mot s est un suffixe d'un mot w s'il existe un mot p tel que w = ps.

  • Les facteurs d'un mot w= a_1\cdots a_n sont les mots a_i\cdots a_j, pour 1\le i\le j\le n.

Les facteurs du mot abac sont les mots ε, a, b, c, ab, ba, ac, aba, bac et abac.

De manière équivalente, un mot x est un facteur d'un mot w s'il existe des mots p,s tel que w = pxs.

  • L'image miroir ou le retourné d'un mot w= a_1\cdots a_n est le mot \tilde w= a_n\cdots a_1. Par exemple, l'image miroir du mot abac est le mot caba.
  • Un palindrome est un mot qui est égal à son image miroir.

Par exemple, le mot abacaba est un palindrome.

  • Un mot x est puissance entière d'un mot y s'il existe un entier positif n tel que x = yn (y répété n fois).
  • Un mot est primitif s'il n'est pas puissance entière d'un autre mot.

Par exemple, le mot bonbon n'est pas primitif, parce qu'il est le carré du mot bon.

Lemme de Levy

Soient x,y,x',y' des mots. Si xy = x'y', alors il existe un mot z tel que x = x'z, y' = zy ou x' = xz, y = zy'.

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

Un résultat fondamental

Si x et y sont deux mots non vides tels que xy = yx, alors ils sont tous deux puissances d'un même mot z.

Morphisme

Une application

h: A^*\to B^*

est un morphisme ou un homomorphism si elle vérifie

h(xy) = h(x)h(y)

pour tous les mots x,y\in A^*. Tout morphisme est déterminé par sa donnée sur les lettres de l'alphabet A. En effet, pour un mot w= a_1a_2\cdots a_n, on a

h(w)= h(a_1)h(a_2)\cdots h(a_n)

Le morphisme de Thue-Morse permet de définir la suite de Prouhet-Thue-Morse. C'est le morphisme \mu: A^*\to A^*, avec A = {0,1}, défini par

μ(0) = 01
μ(1) = 10

En itérant, on obtient

μ(01) = 0110
μ(0110) = 01101001
μ(01101001) = 0110100110010110

Articles connexes

Bibliographie

  • Jean-Michel Autebert, Théorie des langages et des automates, Masson, 1997.
  • Olivier Carton|O. Carton, Langages formels, calculabilité et complexité. Vuibert 2008, (ISBN 978-2-7117-2077-4)

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Mot (mathématiques) de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Mot machine — Mot (informatique) Pour les articles homonymes, voir mot (homonymie). Un mot, en informatique, est l’unité de base manipulée par un microprocesseur. La taille d’un mot s’exprime en bits ou en octets, et est souvent utilisée pour classer les… …   Wikipédia en Français

  • Mot (informatique) — Pour les articles homonymes, voir mot (homonymie). En mathématiques ou en informatique théorique, on appelle mot une suite finie de symboles pris dans un ensemble donné. L ensemble des symboles est souvent appelé alphabet, et ses éléments sont… …   Wikipédia en Français

  • MATHÉMATIQUES , DE LA DIVERSITÉ À L’UNIFICATION — «Ce que nous appelons la réalité objective, c’est, en dernière analyse, ce qui est commun à plusieurs êtres pensants, et pourrait être commun à tous; cette partie commune [...], ce ne peut être que l’harmonie exprimée par des lois mathématiques.» …   Encyclopédie Universelle

  • Mathematiques — Mathématiques Les mathématiques constituent un domaine de connaissances abstraites construites à l aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les transformations. Les mathématiques… …   Wikipédia en Français

  • MATHÉMATIQUES (FONDEMENTS DES) — Au sens premier et fort, le mot «fondement» désigne la base, jugée inébranlable, sur laquelle repose un corps d’énoncés, un système de connaissances, un complexe de croyances ou de conduites. «Reposer sur la base» signifie ici «trouver en elle à… …   Encyclopédie Universelle

  • Mathematiques arabes — Mathématiques arabes Dans l Histoire des mathématiques, on désigne par l expression de mathématiques arabes une des époques les plus importantes du développement de cette science. Il s agit des contributions apportées par les mathématiciens du… …   Wikipédia en Français

  • Mathématiques Arabes — Dans l Histoire des mathématiques, on désigne par l expression de mathématiques arabes une des époques les plus importantes du développement de cette science. Il s agit des contributions apportées par les mathématiciens du monde islamique, du… …   Wikipédia en Français

  • Mot Sans Facteur Carré — En combinatoire, un mot sans facteur carré est un mot qui ne contient pas la même séquence deux fois consécutivement. Pour tout alphabet d au moins trois lettres, il y a une infinité de mots sans facteur carré. Exemples Sur l alphabet {a, b}, l… …   Wikipédia en Français

  • Mot sans facteur carre — Mot sans facteur carré En combinatoire, un mot sans facteur carré est un mot qui ne contient pas la même séquence deux fois consécutivement. Pour tout alphabet d au moins trois lettres, il y a une infinité de mots sans facteur carré. Exemples Sur …   Wikipédia en Français

  • Mathematiques de la relativite generale — Mathématiques de la relativité générale Les mathématiques de la relativité générale se réfèrent à différentes structures et techniques mathématiques utilisées par la théorie de la relativité générale d Albert Einstein. Les principaux outils… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”