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

[Sverest]

Применить к слову $abbbbba$ нормальный алгоритм в алфавите $A=\{a,b\}$ со схемой:

$ab \to a,~b \to \cdot \wedge,~ a \to b$



Как только алгоритм дойдет до точки $b \to \cdot \wedge$ он останавливается и шаги которые за ним не выполняются?

$abbbbba \to abbbba \to abbba$

[Zipfolder]

По идее да, $\to \cdot$ означает терминальный шаг. Однако не сразу: если терминальный шаг невыполним (например, нет буковки $b$), алгоритм будет просмотрен дальше на предмет возможных шагов.

[Sverest]

терминальный шаг может выполняться только один раз?

[Zipfolder]

Э-э, да, он же терминальный. Им и завершается алгоритм.

Другой вариант завершения алгоритма Маркова — нет применимых формул подстановки, то есть в слове нет ни одного из шаблонов в правой части (до стрелочки).