Алгоритм Маркова - Markov algorithm

В теоретической информатике , алгоритм Маркова является строка перезаписи система , которая использует грамматику -как правила действуют на строки символов. Было показано, что марковские алгоритмы являются полными по Тьюрингу , что означает, что они подходят в качестве общей модели вычислений и могут представлять любое математическое выражение из его простой записи. Марковские алгоритмы названы в честь советского математика Андрея Маркова-младшего.

Рефал - это язык программирования, основанный на марковских алгоритмах.

Описание

Обычные алгоритмы вербальны, то есть предназначены для применения к строкам в разных алфавитах.

Определение любого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (алгоритм будет применен к строкам этих символов алфавита) и определения его схемы . Схема нормального алгоритма - это конечный упорядоченный набор так называемых формул подстановки , каждая из которых может быть простой или окончательной . Формулы простой подстановки представлены строками вида , где и - две произвольные строки в алфавите алгоритма (называемые, соответственно, левой и правой частями подстановки формулы). Точно так же формулы окончательной подстановки представлены строками вида , где и - две произвольные строки в алфавите алгоритма. Это предполагает, что вспомогательные символы и не принадлежат алфавиту алгоритма (в противном случае должны быть выбраны два других символа, которые будут выполнять свою роль разделителей левой и правой сторон, которые не входят в алфавит алгоритма). ${\ displaystyle L \ to D}$${\ displaystyle L}$${\ displaystyle D}$${\ displaystyle L \ to \ cdot D}$${\ displaystyle L}$${\ displaystyle D}$${\ displaystyle \ to}$${\ displaystyle \ to \ cdot}$

Вот пример схемы нормального алгоритма в пятибуквенном алфавите : ${\ displaystyle | * abc}$

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

Процесс применения нормального алгоритма к произвольной строке в алфавите этого алгоритма представляет собой дискретную последовательность элементарных шагов, состоящую из следующих. Предположим, что это слово, полученное на предыдущем шаге алгоритма (или исходное слово , если текущий шаг является первым). Если в формулах подстановки нет левой части, которая включена в , то алгоритм завершается, и результатом его работы считается строка . В противном случае выбирается первая из формул подстановки, в которой включены левые части . Если формула подстановки имеет вид , то из всех возможных представлений строки формы (где и - произвольные строки) выбирается самое короткое . Затем алгоритм завершается и результат его работы считается . Однако, если эта формула подстановки имеет форму , то из всех возможных представлений строки выбирается форма с самой короткой , после чего строка считается результатом текущего шага, при условии для дальнейшей обработки на следующем этапе. ${\ displaystyle V}$${\ displaystyle V '}$${\ displaystyle V}$${\ displaystyle V '}$${\ displaystyle V '}$${\ displaystyle V '}$${\ displaystyle L \ to \ 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}$

Например, процесс применения алгоритма описано выше со словом приводит к последовательности слов , , , , , , , , , и , после чего алгоритм останавливается с результатом . ${\ 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 ||}$

Другие примеры см. Ниже.

Любой нормальный алгоритм эквивалентен некоторой машине Тьюринга , и наоборот - любая машина Тьюринга эквивалентна некоторому нормальному алгоритму. Вариант тезиса Чёрча-Тьюринга, сформулированный по отношению к нормальному алгоритму, называется «принципом нормализации».

Нормальные алгоритмы оказались удобным средством построения многих разделов конструктивной математики . Более того, в определение нормального алгоритма входит ряд идей, используемых в языках программирования, направленных на обработку символьной информации - например, в Refal .

Алгоритм

В Правила представляют собой последовательность пар строк, обычно представленных в виде шаблона → замены . Каждое правило может быть обычным или завершающим.

Учитывая входную строку:

1. Проверьте Правила в порядке сверху вниз, чтобы увидеть, можно ли найти какой-либо из шаблонов во входной строке.
2. Если ничего не найдено, алгоритм останавливается.
3. Если один (или несколько) найден, используйте первый из них, чтобы заменить крайнее левое вхождение совпадающего текста во входной строке его заменой .
4. Если только что примененное правило было завершающим, алгоритм останавливается.
5. Переходите к шагу 1.

Обратите внимание, что после каждого применения правила поиск начинается заново с первого правила.

Пример

В следующем примере показаны основные операции алгоритма Маркова.

Правила

1. «А» -> «яблоко»
2. «Б» -> «сумка»
3. "S" -> "магазин"
4. "T" -> "the"
5. "магазин" -> "мой брат"
6. "никогда не использовался" -> . "правило прекращения"

Строка символов

"Я купил B of As у T S."

Исполнение

Если алгоритм применяется к приведенному выше примеру, строка символа изменится следующим образом.

1. "Я купил B of As у T S."
2. «Я купил яблоко в компании Т. С.»
3. «Я купил сумку яблок в ТС.»
4. «Я купил пакет яблок в магазине Т».
5. «Я купила в магазине сумку яблок».
6. «Я купил у брата мешок яблок».

Затем алгоритм завершится.

Другой пример

Эти правила дают более интересный пример. Они заменяют двоичные числа своими унарными аналогами. Например, 101 будет переписан в строку из 5 последовательных тактов.

Правила

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

Строка символов

«101»

Исполнение

Если алгоритм применяется к приведенному выше примеру, он завершится после следующих шагов.

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

Смотрите также

• Туэ (язык программирования)
• Формальная грамматика

Рекомендации

• Караччоло ди Форино, А. Языки обработки строк и обобщенные марковские алгоритмы. В языках и методах манипулирования символами, DG Bobrow (Ed.), North-Holland Publ. Co., Амстердам, Нидерланды, 1968, стр. 191–206.
• Андрей Андреевич Марков (1903-1979) 1960. Теория алгоритмов. Переводы Американского математического общества, серии 2, 15, 1-14.

внешняя ссылка

• Yad Studio - IDE и интерпретатор марковских алгоритмов (Open Source)
• Интерпретатор марковского алгоритма
• Интерпретатор марковского алгоритма
• Интерпретаторы алгоритмов Маркова в Rosetta-Code