Подразделы

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

Дата и время

06/01/2026 07:41:40

Авторизация

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

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

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

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

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

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

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

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

--

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

`"1" -> "0a"`\
`"a0" -> "0aa"`\
`"0" ->`

Выполнение:

```text
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"`

---

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

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

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

--

[Эмулятор и сборник задачник по НАМ](blockly/nam.html)

Назад

Подразделы

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

Дата и время

Авторизация

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

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