Краткое описание нормальных алгоритмов Маркова

Лекция 14. Нормальные алгоритмы Маркова

Вопросы лекции:

14.1 Краткое описание нормальных алгоритмов Маркова.

14.2 Определение НАМ.

14.3 Правила выполнения НАМ.

14.4 Пример составления НАМ

Литература:Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. – 3-е изд. – М.: «Вильямс», 2006. – 720 с.

Интересной особенностью нормальных алгоритмов Маркова (НАМ) является то, что в них используется лишь одно элементарное действие – так называемая подстановка, которая определяется следующим образом.

Формулой подстановки называется запись вида αβ (читается «α заменить на β»), где α и β – любые слова (возможно, и пустые). При этом α называется левой частью формулы, а β – правой частью.

Сама подстановка (как действие) задается формулой подстановки и применяется к некоторому слову Р. Суть операции сводится к тому, что в слове Р отыскивается часть, совпадающая с левой частью этой формулы (т. е. с α), и она заменяется на правую часть формулы (т. е. на β). При этом остальные части слова Р (слева и справа от α) не меняются. Получившееся слово R называют результатом подстановки. Условно это можно изобразить так (рисунок 14.1).

Рисунок 14.1 – Результат подстановки по формуле подстановки α→β

Необходимые уточнения:

1. Если левая часть формулы подстановки входит в слово Р, то говорят, что эта формула применима к Р. Но если α не входит в Р, то формула считается неприменимой к Р, и подстановка не выполняется.

2. Если левая часть α входит в Р несколько раз, то на правую часть β, по определению, заменяется только первое вхождение α в Р (рисунок 14.2).

Рисунок 14.2 – Результат подстановки по формуле подстановки αβ, когда заменяется только первое вхождение α в Р

3. Если правая часть формулы подстановки – пустое слово, то подстановка αсводится к вычеркиванию части α из Р (отметим попутно, что в формулах подстановки не принято как-либо обозначать пустое слово) (рисунок 14.3).

Рисунок 14.3 – Результат подстановки по формуле подстановки α→

4. Если в левой части формулы подстановки указано пустое слово, то подстановка β сводится, по определению, к приписыванию β слева к слову P (рисунок 14.4).

Рисунок 14.4 – Результат подстановки по формуле подстановки →β