Нормальные алгоритмы.
Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах. Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам в котором алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор т. н. формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида , где L и D — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида , где L и D — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы и не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы). Процесс применения нормального алгоритма к произвольному слову V в алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть V' — слово, полученное на предыдущем шаге работы алгорифма (или исходное слово V, если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в V', то работа алгоритма считается завершённой, и результатом этой работы считается слово V'. Иначе среди формул подстановки, левая часть которых входит в V', выбирается самая верхняя. Если эта формула подстановки имеет вид , то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего работа алгоритма считается завершённой с результатом RDS. Если же эта формула подстановки имеет вид , то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего слово RDS считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге. Использование алгоритма Маркова для преобразований над строками: Правила: «А» → «апельсин» «кг» → «килограмм» «М» → «магазинчике» «Т» → «том» «магазинчике» → ·"ларьке" (заметьте, это заключительная формула!) «в том ларьке» → «на том рынке» Исходная строка: «Я купил кг Аов в Т М.» При выполнении алгоритма строка претерпевает следующие изменения: «Я купил кг апельсинов в Т М.» «Я купил килограмм апельсинов в Т М.» «Я купил килограмм апельсинов в Т магазинчике.» «Я купил килограмм апельсинов в том магазинчике.» «Я купил килограмм апельсинов в том ларьке.»
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|