Марковский алгоритм

Эта статья включает в себя список литературы , связанной литературы или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Май 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

Описание [ править ]

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

Определение любого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (алгоритм будет применен к строкам этих символов алфавита) и определения его схемы . Схема нормального алгоритма - это конечный упорядоченный набор так называемых формул подстановки , каждая из которых может быть простой или окончательной . Формулы простой подстановки представлены строками вида , где и - две произвольные строки в алфавите алгоритма (называемые, соответственно, левой и правой частями подстановки формулы). Аналогичным образом формулы окончательной подстановки представлены строками вида , где${\ 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