Accueil / Mots Combinatoire / Monoïde libre

Morphismes de mots.

Monoïde libre

Un ensemble A, l'alphabet, dont les éléments sont appelés lettres..
(Prendre par exemple l'alphabet de 4 lettres A={a, b, c, d} ou l'alphabet binaire B={0,1}).

Les mots sont les suites finies (a1, a2, a3,...,an) de lettres ai de l'alphabet A. Le plus souvent les mots seront écrits sous la forme a1a2a3...an, ce qui amène à identifier la simple lettre a et la suite (a) (c'est l'injection naturelle de A dans l'ensemble A* des mots).
L'ensemble des mots est A*.

L'opération de concaténation des mots : si u et v sont deux mots, u v = uv, c'est-à-dire (u) (v) = (uv), ou encore :
(a1a2a3...an)   (b1b2b3...bp) = (a1a2a3...anb1b2b3...bp).

Le mot vide est l'élément neutre, noté 1, de cette opération. 1w = w1 = w
La concaténation est associative.

Le monoïde libre A* : La structure (A* , concaténation) est une structure de monoïde.

Un morphisme f du monoïde M vers le monoïde N est compatible avec les opérations des deux monoïdes M et N et applique l'élément neutre 1M du premier sur l'élément neutre 1N du second.
f(u v) = f(u) f(v) et f(1M) = 1N.

Pour toute application h de l'alphabet A dans un monoïde M, il existe un unique morphisme f de A* dans M et on a   h = f ° i, où i est l'injection naturelle de A dans A*.
Et donc pour tout morphisme de A* dans M, il suffit de donner les images des mots d'une seule lettre de A.

Par exemple l'alphabet ternaire {a, b, c}, le mot initial 'a' et le morphisme f : f(a) = abc, f(b) = ac, f(c) = b de A* vers A*.

Les liens comme celui-ci [Mus.] font entendre un air de musique composé automatiquement en utilisant le début du mot infini. Voir aussi la page récapitulative.

Exemples

N'utiliser que des lettres minuscules ou des chiffres. Le nombre de morphismes est limité à 26.

Mot infini de Prouhet-Thue-Morse.

[Mus.] Suite de Prouhet-Thue-Morse de mot initial 'a' et de morphisme 'a -> ab, b -> ba'.

Suite de Rudin-Shapiro

[Mus.] 1ère étape : Initialiser : avec le mot 'a' et le morphisme ' a -> ab, b -> ac, c -> db, d -> dc'.
Construire un pot suffisamment grand avant de procéder à l'étape suivante pour terminer
2ème étape : Appliquez une fois le morphisme 'a -> +, b -> +, c -> -, d -> -'

Fibonacci

[Mus.] Croissance d'une population de lapins. '0' représente un jeune lapin et '1' un lapin plus âgé. Utiliser le Morphisme pour simuler l'évolution de l'élevage de lapins.
Voir la page sur la suite de Fibonacci.

Tribonacci

[Mus.] La suite dite de tribonacci est construite sur l'alphabet ternaire {1, 2, 3}, à l'aide du morphisme '1 -> 12, 2 -> 13, 3 -> 1' .    Initialisations.
(Voir aussi la suite A000073 de Sloane).

Suite Look and Say 'Je dis ce que je lis'

[Mus.] Il s'agit ici d'une utilisation détournée du programme, appliquée à la construction de la suite A005150, appelée Look and Say sequence. J. H. Conway qui appelait cette suite 'audioactive decay' en donna en 1987 la règle de génération et démontra différentes propriétés dont en particulier le 'Cosmological Theorem'. Sa preuve rédigée "à la main" est perdue. Cf. les articles indiqués dans les liens.
Le premier terme est 1, le second est 'un 1' = 11, le troisième est 'deux 1' = 21, puis 'un 2 un 1'= 1211, etc.
Pour construire la suite il faut d'abord l'[initialiser]. et ensuite cliquer sur [effectuer] autant de fois que soubaité.
Notez les longueurs des mots successifs obtenus : A005341


Morphismes
Morphisme


Mots

      | s | =        



  Taille maximale



Autres exemples

[Mus.] 5 éléments.
Application à la simplification de chemins tracés sur une grille ou un quadrillage, dans le plan.


Liens




Accueil / Mots Combinatoire / Monoïde libre

















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014