*Нормальный алгоритм* (алгорифм Маркова, НАМ) -- это модель вычисления, заданная кортежем `M = (Sigma, Pi)`, где
1. `Sigma` -- это алфавит
2. `Pi` -- схема алгоритма, содержащая правила подстановки вида `alpha -> beta` (простое) или
`alpha ->* beta` (терминальное), где `alpha` и `beta` - последовательности символов из `Sigma`, возможно пустые.
Алгоритм выполняется циклически следующим образом: просматриваются правила подстановки, начиная с 1-го, если `alpha` входит в текущее слово, то самое левое вхождение `alpha` заменяется на `beta`.
Алгоритм заканчивается, если не удается применить одного правила или было применено терминальное правило.
Любой нормальный алгоритм эквивалентен некоторой МТ, и наоборот — любая МТ эквивалентна некоторому нормальному алгоритму.
--
Пример нормального алгоритма для перевода двоичного числа в соответствующее количество букв ``a``:
Для любой МТ можно можно построить эквивалентный ей НАМ и наоборот.
Построение НАМ по МТ выполняется достаточно легко.
Строку на ленте МТ нужно дополнить слева и справа символами пустой ячейки.
Текущее состояние МТ можно записать как символ `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"`
---
##### Задания для практики
Определите НАМ, решающий следующую задачу:
1. В строке из букв a,b,c упорядочить буквы по алфавиту
2. В строке из букв a,b,c удалить последовательности из двух или более одинаковых букв
3. В строке из букв a,b оставить одну букву, встречающуюся чаще всего. При равенстве должна остаться пустая строка.
--
[Эмулятор и сборник задачник по НАМ](blockly/nam.html)