Algorithme de Markov

Les règles sont une suite de couples de chaînes, habituellement présentées sous la forme schéma → remplacement. Certaines règles peuvent en outre être qualifiées de terminales.

Étant donné une chaîne d'entrée :

1. Vérifier les règles dans l'ordre, du haut vers le bas, jusqu'à en trouver une dont le schéma peut être trouvé dans la chaîne d'entrée (ainsi, si plusieurs schémas conviennent, seule la première règle rencontrée sera prise en compte).
2. Si une telle règle n'est pas trouvée, l'algorithme s'arrête.
3. Sinon, l'occurrence la plus à gauche du schéma dans la chaîne d'entrée est remplacée par la chaîne de remplacement donnée par la règle.
4. Si la règle est terminale, l'algorithme s'arrête.
5. Recommencer à la première étape.

Les règles suivantes réécrivent un nombre binaire en version unaire ; par exemple, 101 sera réécrit comme une chaîne de 5 barres consécutives.

• Caracciolo di Forino, A. String processing languages and generalized Markov algorithms. In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 191–206.
• Andreï Markov 1960. The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14.

• « Online Markov algorithm interpreter »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}
• Markov algorithm interpreter
• Markov algorithm interpreter
• Joran Bigalet, « Algorithmes de Markov » (consulté le 29 août 2013)
• Vincent Laviron, « Algorithmes de Markov » (consulté le 29 août 2013)

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Markov algorithm » (voir la liste des auteurs).