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

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

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

Описание

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

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

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

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

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

Алгоритм

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

Учитывая Вход нить:

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. "|||||"

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

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

Примечания

1. Новый вид науки [1]

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

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

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

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