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