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

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

Нормальным алгоритмом Маркова (НАМ) называется непустой конечный упорядоченный набор формул подстановки:

(14.1)

В этих формулах могут использоваться два вида стрелок: обычная стрелка () и стрелка «с хвостиком» (). Формула с обычной стрелкой называется обычной формулой, а формула со стрелкой «с хвостиком» – заключительной формулой. Разница между ними объясняется чуть ниже.

Записать алгоритм в виде НАМ – значит предъявить такой набор формул.

Прежде всего, задается некоторое входное слово Р. Где именно оно записано – не важно, в НАМ этот вопрос не оговаривается.

Работа НАМ сводится к выполнению последовательности шагов. На каждом шаге входящие в НАМ формулы подстановки просматриваются сверху вниз и выбирается первая из формул, применимых к входному слову Р, т. е. самая верхняя из тех, левая часть которых входит в Р. Далее выполняется подстановка согласно найденной формуле. Получается новое слово Р′.

На следующем шаге это слово Р′ берется за исходное и к нему применяется та же самая процедура, т. е. формулы снова просматриваются сверху вниз начиная с самой верхней и ищется первая формула, применимая к слову Р′, после чего выполняется соответствующая подстановка и получается новое слово Р′′. И так далее (рисунок 14.5).

Рисунок 14.5 – Иллюстрация правила выполнения НАМ

Следует обратить особое внимание на тот факт, что на каждом шаге формулы в НАМ всегда просматриваются начиная с самой первой.

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

1. Если на очередном шаге была применена обычная формула (αβ), то работа НАМ продолжается.

2. Если же на очередном шаге была применена заключительная формула (αβ), то после её применения работа НАМ прекращается. То слово, которое получилось в этот момент, и есть выходное слово, т. е. результат применения НАМ к входному слову.

Как видно, разница между обычной и заключительной формулами подстановки проявляется лишь в том, что после применения обычной формулы работа НАМ продолжается, а после заключительной формулы – прекращается.

3. Если на очередном шаге к текущему слову неприменима ни одна формула, то и в этом случае работа НАМ прекращается, а выходным словом считается текущее слово.

Таким образом, НАМ останавливается по двум причинам: либо была применена заключительная формула, либо ни одна из формул не подошла. То и другое считается «хорошим» окончанием работы НАМ. В обоих случаях говорят, что НАМ применим к входному слову.

Однако может случиться и так, что НАМ никогда не остановится; это происходит, когда на каждом шаге есть применимая формула и эта формула обычная. Тогда говорят, что НАМ неприменим к входному слову. В этом случае ни о каком результате нет и речи.

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

Рассмотрим пример, в который демонстрируются типичные приёмы составления НАМ.

Как и в случае машины Тьюринга, для сокращения формулировки задачи будем использовать следующие соглашения:

– буквой Р будем обозначать входное слово;

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

Кроме того, в примере будем справа от формул подстановки указывать их номера. Эти номера не входят в формулы, а нужны для ссылок на формулы при показе пошагового выполнения НАМ.

Пример 1 (вставка и удаление символов).

Дано А={a,b,c,d}. В слове Р требуется заменить первое вхождение подслова bb на ddd и удалить все вхождения символа c.

Например: abbcabbca adddabba