Medrikon.ru

Народный сайт medrikon.ru

Метки: Нормальный алгоритм маркова служебные символы, нормальный алгоритм маркова алфавит, нормальный алгоритм маркова это.

Норма́льный алгори́тм Ма́ркова (НАМ) — один из стандартных способов формального определения понятия алгоритма, так же как и машина Тьюринга. Понятие нормального алгоритма введено А. А. Марковым в конце 1940-х годов. Традиционно, когда говорят об алгоритмах Маркова, используют слово «алгорифм».

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

Содержание

Описание

Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах. Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам из символов которого алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор т. н. формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида , где и  — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида , где и  — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы и не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

Примером схемы нормального алгоритма в пятибуквенном алфавите может служить схема

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

Процесс применения нормального алгоритма к произвольному слову в алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть  — слово, полученное на предыдущем шаге работы алгорифма (или исходное слово , если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в , то работа алгоритма считается завершённой, и результатом этой работы считается слово . Иначе среди формул подстановки, левая часть которых входит в , выбирается самая верхняя. Если эта формула подстановки имеет вид , то из всех возможных представлений слова в виде выбирается такое, при котором  — самое короткое, после чего работа алгоритма считается завершённой с результатом . Если же эта формула подстановки имеет вид , то из всех возможных представлений слова в виде выбирается такое, при котором  — самое короткое, после чего слово считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.

Например, в ходе процесса применения алгорифма с указанной выше схемой к слову последовательно возникают слова , , , , , , , , , и , после чего алгорифм завершает работу с результатом . Другие примеры смотрите ниже.

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

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

Примеры

Пример 1

Использование алгоритма Маркова для преобразований над строками:

Правила:

  1. «А» → «апельсин»
  2. «кг» → «килограмм»
  3. «М» → «магазинчике»
  4. «Т» → «том»
  5. «магазинчике» →• «ларьке» (заключительная формула)
  6. «в том ларьке» → «на том рынке»

Исходная строка:

«Я купил кг Аов в Т М.»

При выполнении алгоритма строка претерпевает следующие изменения:

  1. «Я купил кг апельсинов в Т М.»
  2. «Я купил килограмм апельсинов в Т М.»
  3. «Я купил килограмм апельсинов в Т магазинчике.»
  4. «Я купил килограмм апельсинов в том магазинчике.»
  5. «Я купил килограмм апельсинов в том ларьке.»

На этом выполнение алгоритма завершится (так как будет достигнута формула № 5, которую мы сделали заключительной).

Пример 2

Данный алгоритм преобразует двоичные числа в «единичные», то есть на выходе получается строка из N единичек, если на входе у нас было N в двоичной системе. Например, 101 преобразуется в 5 единиц:

Правила:

  1. «|0» → "0||"
  2. «1» → "0|"
  3. «0» → "" (пустая строка)

Исходная строка:

«101»

Выполнение:

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

См. также

Прочие абстрактные исполнители и формальные системы вычислений

Примечания


Tags: Нормальный алгоритм маркова служебные символы, нормальный алгоритм маркова алфавит, нормальный алгоритм маркова это.