Algoritmo de Markov - Markov algorithm

En informática teórica , un algoritmo de Markov es un sistema de reescritura de cadenas que utiliza reglas similares a la gramática para operar sobre cadenas de símbolos. Se ha demostrado que los algoritmos de Markov son Turing completos , lo que significa que son adecuados como modelo general de cálculo y pueden representar cualquier expresión matemática a partir de su notación simple. Los algoritmos de Markov llevan el nombre del matemático soviético Andrey Markov, Jr.

Refal es un lenguaje de programación basado en algoritmos de Markov.

Descripción

Los algoritmos normales son verbales, es decir, destinados a ser aplicados a cadenas en diferentes alfabetos.

La definición de cualquier algoritmo normal consta de dos partes: la definición del alfabeto del algoritmo (el algoritmo se aplicará a las cadenas de estos símbolos alfabéticos) y la definición de su esquema . El esquema de un algoritmo normal es un conjunto finito ordenado de las llamadas fórmulas de sustitución , cada una de las cuales puede ser simple o final . Las fórmulas de sustitución simple están representadas por cadenas de la forma , donde y son dos cadenas arbitrarias en el alfabeto del algoritmo (llamados, respectivamente, los lados izquierdo y derecho de la sustitución de fórmulas). De manera similar, las fórmulas de sustitución final se representan mediante cadenas de la forma , donde y son dos cadenas arbitrarias en el alfabeto del algoritmo. Esto supone que los caracteres auxiliares y no pertenecen al alfabeto del algoritmo (de lo contrario, se deben seleccionar otros dos caracteres para realizar su papel como divisores de los lados izquierdo y derecho, que no están en el alfabeto del algoritmo). ${\ Displaystyle L \ to D}$${\ Displaystyle L}$${\ Displaystyle D}$${\ Displaystyle L \ a \ cdot D}$${\ Displaystyle L}$${\ Displaystyle D}$${\ Displaystyle \ to}$${\ Displaystyle \ to \ cdot}$

A continuación, se muestra un ejemplo de un esquema de algoritmo normal en el alfabeto de cinco letras : ${\ Displaystyle | * abc}$

${\ Displaystyle \ left \ {{\ begin {matrix} | b & \ to & ba | \\ ab & \ to & ba \\ b & \ to & \\ {*} | & \ to & b * & \\ {*} & \ a & c & \\ | c & \ a & c \\ ac & \ to & c | \\ c & \ to \ cdot \ end {matriz}} \ right.}$

El proceso de aplicar el algoritmo normal a una cadena arbitraria en el alfabeto de este algoritmo es una secuencia discreta de pasos elementales, que consta de lo siguiente. Supongamos que es la palabra obtenida en el paso anterior del algoritmo (o la palabra original , si el paso actual es el primero). Si de las fórmulas de sustitución no hay un lado izquierdo que esté incluido en el , entonces el algoritmo termina y el resultado de su trabajo se considera la cadena . De lo contrario, se selecciona la primera de las fórmulas de sustitución cuyos lados izquierdos están incluidos . Si la fórmula de sustitución es de la forma , de todas las representaciones posibles de la cadena de la forma (donde y son cadenas arbitrarias) se elige la que tenga la más corta . Entonces el algoritmo termina y se considera que el resultado de su trabajo es . Sin embargo, si esta fórmula de sustitución es de la forma , de todas las posibles representaciones de la cadena se elige la forma con la más corta , después de lo cual se considera que la cadena es el resultado del paso actual, sujeto para continuar con el procesamiento en el siguiente paso. ${\ Displaystyle V}$${\ Displaystyle V '}$${\ Displaystyle V}$${\ Displaystyle V '}$${\ Displaystyle V '}$${\ Displaystyle V '}$${\ Displaystyle L \ a \ cdot D}$${\ Displaystyle V '}$${\ Displaystyle RLS}$${\ Displaystyle R}$${\ Displaystyle S}$${\ Displaystyle R}$${\ Displaystyle RDS}$${\ Displaystyle L \ to D}$${\ Displaystyle V '}$${\ Displaystyle RLS}$${\ Displaystyle R}$${\ Displaystyle RDS}$

Por ejemplo, el proceso de aplicar el algoritmo descrito anteriormente para la palabra resultados en la secuencia de palabras , , , , , , , , , y , después de lo cual el algoritmo se detiene con el resultado . ${\ Displaystyle | * ||}$${\ Displaystyle | b * |}$${\ Displaystyle ba | * |}$${\ Displaystyle a | * |}$${\ Displaystyle a | b *}$${\ displaystyle aba | *}$${\ Displaystyle baa | *}$${\ Displaystyle aa | *}$${\ Displaystyle aa | c}$${\ displaystyle aac}$${\ displaystyle ac |}$${\ Displaystyle c ||}$${\ Displaystyle ||}$

Para ver otros ejemplos, consulte a continuación.

Cualquier algoritmo normal es equivalente a alguna máquina de Turing y viceversa; cualquier máquina de Turing es equivalente a algún algoritmo normal. Una versión de la tesis de Church-Turing formulada en relación con el algoritmo normal se denomina "principio de normalización".

Los algoritmos normales han demostrado ser un medio conveniente para la construcción de muchas secciones de la matemática constructiva . Además, inherente a la definición de un algoritmo normal hay una serie de ideas utilizadas en lenguajes de programación destinados a manejar información simbólica, por ejemplo, en Refal .

Algoritmo

Las Reglas son una secuencia de pares de cadenas, generalmente presentadas en forma de patrón → reemplazo . Cada regla puede ser ordinaria o terminante.

Dada una cadena de entrada :

1. Verifique las Reglas en orden de arriba a abajo para ver si se puede encontrar alguno de los patrones en la cadena de entrada .
2. Si no se encuentra ninguno, el algoritmo se detiene.
3. Si se encuentra uno (o más), utilice el primero de ellos para reemplazar la aparición más a la izquierda del texto coincidente en la cadena de entrada con su reemplazo .
4. Si la regla que se acaba de aplicar era de terminación, el algoritmo se detiene.
5. Vaya al paso 1.

Tenga en cuenta que después de cada aplicación de regla, la búsqueda comienza desde la primera regla.

Ejemplo

El siguiente ejemplo muestra el funcionamiento básico de un algoritmo de Markov.

Normas

1. "A" -> "manzana"
2. "B" -> "bolsa"
3. "S" -> "tienda"
4. "T" -> "el"
5. "la tienda" -> "mi hermano"
6. "nunca usado" -> . "regla de terminación"

Cadena de símbolo

"Compré una B de As de T S."

Ejecución

Si el algoritmo se aplica al ejemplo anterior, la cadena de símbolo cambiará de la siguiente manera.

1. "Compré una B de As de T S."
2. "Compré una B de manzanas de T S."
3. "Compré una bolsa de manzanas de T S."
4. "Compré una bolsa de manzanas en la tienda T".
5. "Compré una bolsa de manzanas en la tienda".
6. "Le compré una bolsa de manzanas a mi hermano".

Entonces el algoritmo terminará.

Otro ejemplo

Estas reglas dan un ejemplo más interesante. Reescriben números binarios en sus contrapartes unarias. Por ejemplo, 101 se reescribirá en una cadena de 5 compases consecutivos.

Normas

1. "| 0" -> "0 ||"
2. "1" -> "0 |"
3. "0" -> ""

Cadena de símbolo

"101"

Ejecución

Si el algoritmo se aplica al ejemplo anterior, terminará después de los siguientes pasos.

1. "101"
2. "0 | 01"
3. "00 || 1"
4. "00 || 0 |"
5. "00 | 0 |||"
6. "000 |||||"
7. "00 |||||"
8. "0 |||||"
9. "|||||"

Ver también

• Thue (lenguaje de programación)
• Gramática formal

Referencias

• Caracciolo di Forino, A. Lenguajes de procesamiento de cadenas y algoritmos de Markov generalizados. En Lenguajes y técnicas de manipulación de símbolos, DG Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, Países Bajos, 1968, págs. 191–206.
• Andrey Andreevich Markov (1903-1979) 1960. La teoría de los algoritmos. Traducciones de la American Mathematical Society, series 2, 15, 1-14.

enlaces externos

• Yad Studio - IDE e intérprete de algoritmos de Markov (código abierto)
• Intérprete del algoritmo de Markov
• Intérprete del algoritmo de Markov
• Intérpretes del algoritmo de Markov en Rosetta-Code