Подразделы

Другие разделы

Дата и время

09/04/2025 22:13:37

Авторизация

Вычислительные основы

Реальные компьютеры vs. модели вычислений Детерминированный конечный автомат Машина Тьюринга Нормальный алгоритм Маркова Теория рекурсивных функций * Практическое использование

Нормальный алгоритм Маркова

Нормальный алгоритм (алгорифм Маркова, НАМ) – это модель вычисления, заданная кортежем $M = (Sigma, Pi)$ , где

$Sigma$ – это алфавит
$Pi$ – схема алгоритма, содержащая правила подстановки вида $alpha -> beta$ (простое) или $alpha ->* beta$ (терминальное), где $alpha$ и $beta$ - последовательности символов из $Sigma$ , возможно пустые.

Алгоритм выполняется циклически следующим образом: просматриваются правила подстановки, начиная с 1-го, если $alpha$ входит в текущее слово, то самое левое вхождение $alpha$ заменяется на $beta$ .

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

Любой нормальный алгоритм эквивалентен некоторой МТ, и наоборот — любая МТ эквивалентна некоторому нормальному алгоритму.

Пример нормального алгоритма для перевода двоичного числа в соответствующее количество букв a:

$"1" -> "0a"$
$"a0" -> "0aa"$
$"0" ->$

Выполнение:

101
0a01
0a00a
00aa0a
00a0aaa
000aaaaa
00aaaaa
0aaaaa
aaaaa

Для любой МТ можно можно построить эквивалентный ей НАМ и наоборот. Построение НАМ по МТ выполняется достаточно легко.

Строку на ленте МТ нужно дополнить слева и справа символами пустой ячейки. Текущее состояние МТ можно записать как символ $q_i$ перед текущим символом. Для старта из состояния $q_0$ последнее правило НАМ должно выглядеть как:
$square -> square q_0$
Правило НАМ для перехода вправо с изменением символа $x$ на $y$ , а состояния с $q_i$ на $q_j$ будет выглядеть так:
$q_i "x" -> "y" q_j$
Для перехода влево нужно написать правила для всех возможных символов $"z"$ :
$"z" q_i "x" -> q_j "z" "y"$
Переход в состояние $q_{ac cept}$ в НАМ превращается в терминальное правило:
$q_i "x" ->* "x"$

Задания для практики

Определите НАМ, решающий следующую задачу:

В строке из букв a,b,c упорядочить буквы по алфавиту
В строке из букв a,b,c удалить последовательности из двух или более одинаковых букв
В строке из букв a,b оставить одну букву, встречающуюся чаще всего. При равенстве должна остаться пустая строка.

Эмулятор и сборник задачник по НАМ