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

Алгоритм Маркова дозволяє змінювати слова заміною їх частин. Даний алгоритм має безліч значень, а заміна проводиться підстановкою.

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

Посилання на основну публікацію