Нормальні алгоритми

Застосування нормального алгоритму до слова s полягає в такому.

• В заданому списку формул підстановок знаходять першу формулу, ліва частина якої входить до слова s. Знаходять перше входження цієї частини в слові s і замість цього входження підставляють праву частину формули. Це дасть нове слово s₁.
• З отриманим словом s₁ повторюють попередній крок.

Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритму. Крім того, постулюють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із заключних формул підстановки, тобто, формул виду p →• q. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритму до слова s.

Як приклад схеми нормального алгоритму можна навести наступну схему в алфавіті з п'яти літер |*abc, яка реалізовує унарне множення:

${\displaystyle \left\{{\begin{matrix}|b&\to &ba|\\ab&\to &ba\\b&\to &\\{*}|&\to &b*\\{*}&\to &c\\|c&\to &c\\ac&\to &c|\\c&\to \bullet &\end{matrix}}\right.}$

При застосуванні алгоритму з наведеною вище схемою до слова ${\displaystyle |*||}$ будуть отримуватись слова:

1. ${\displaystyle |b*|}$,
2. ${\displaystyle ba|*|}$,
3. ${\displaystyle a|*|}$,
4. ${\displaystyle a|b*}$,
5. ${\displaystyle aba|*}$,
6. ${\displaystyle baa|*}$,
7. ${\displaystyle aa|*}$,
8. ${\displaystyle aa|c}$,
9. ${\displaystyle aac}$,
10. ${\displaystyle ac|}$
11. ${\displaystyle c||}$,
12. ${\displaystyle ||}$.

Результатом застосування буде слово ${\displaystyle ||}$, що узгоджується з ${\displaystyle |*||=||}$.

Даний алгоритм перетворює двійкові числа в «унарні» (в яких записом цілого невід'ємного числа N є рядок з N паличок). Наприклад, двійкове число 101 перетвориться в 5 паличок: |||||.

{ 0, 1, | }.

1. 1 → 0|,
2. |0 → 0||,
3. 0 → (порожній рядок).

При застосуванні алгоритму з наведеною вище схемою до слова 101 будуть отримуватись слова:

1. 0|01,
2. 0|00|,
3. 00||0|,
4. 00|0|||,
5. 000|||||,
6. 00|||||,
7. 0|||||,
8. |||||.

• Yad Studio — IDE та інтерпритатор для Нормальних Алгоритмів Маркова (Open Source)