4. Если в левой части формулы подстановки указано пустое слово, то подстановка сводится, по определению, к приписыванию в слева к слову p:
Из этого правила вытекает очень важный факт: формула с пустой левой частью применима к любому слову. Отметим также, что формула с пустыми левой и правой частями не меняет слово.
Определение НАМ
Нормальным
алгоритмом Маркова (НАМ) называется
непустой конечный упорядоченный набор
формул подстановки
В этих формулах могут использоваться два вида стрелок: обычная стрелка (→) и стрелка «с хвостиком» (→). Формула с обычной стрелкой называется обычной формулой, а формула со стрелкой «с хвостиком» - заключительной формулой. Разница между ними объясняется чуть ниже.
Записать алгоритм в виде НАМ - значит предъявить такой набор формул.
1.2 Правила выполнения нам
Прежде всего, задается некоторое входное слово Р. Где именно оно записано - не важно, в НАМ этот вопрос не оговаривается.
Работа НАМ сводится к выполнению последовательности шагов. На каждом шаге входящие в НАМ формулы подстановки просматриваются сверху вниз и выбирается первая из формул, применимых к входному слову Р, т. е. самая верхняя из тех, левая часть которых входит в Р. Далее выполняется подстановка согласно найденной формуле. Получается новое слово Р'.
На
следующем шаге это слово
Р'
берется за исходное и к нему применяется
та же самая процедура, т.е. формулы снова
просматриваются сверху вниз начиная с
самой верхней и ищется первая формула,
применимая к слову Р, после чего
выполняется соответствующая подстановка
и получается новое слово
Р ".
И так далее:
Следует обратить особое внимание на тот факт, что на каждом шаге формулы в НАМ всегда просматриваются начиная с самой первой.
Необходимые уточнения:
Если на очередном шаге была применена обычная формула (α→β), то работа НАМ продолжается.
Если же на очередном шаге была применена заключительная формула (α→β), то после её применения работа НАМ прекращается. То слово, которое получилось в этот момент, и есть выходное слово, т.е. результат применения НАМ к входному слову.
Как видно, разница между обычной и заключительной формулами подстановки проявляется лишь в том, что после применения обычной формулы работа НАМ продолжается, а после заключительной формулы - прекращается.
Если на очередном шаге к текущему слову неприменима ни одна формула, то и в этом случае работа НАМ прекращается, а выходным словом считается текущее слово.
Таким образом, НАМ останавливается по двум причинам: либо была применена заключительная формула, либо ни одна из формул не подошла. То и другое считается «хорошим» окончанием работы НАМ. В обоих случаях говорят, что НАМ применим к входному слову.
Однако может случиться и так, что НАМ никогда не остановится; это происходит, когда на каждом шаге есть применимая формула и эта формула обычная. Тогда говорят, что НАМ неприменим к входному слову. В этом случае ни о каком результате нет и речи.
2.Практическая часть: Примеры на составление нам
Рассмотрим примеры, в которых демонстрируются типичные приёмы составления НАМ.
Как и в случае машины Тьюринга, для сокращения формулировки задач будем использовать следующие соглашения:
буквой Р будем обозначать входное слово;
буквой А будем обозначать алфавит входного слова, т.е. набор тех символов, которые и только которые могут входить во входное слово Р (но в процессе выполнения НАМ в обрабатываемых словах могут появляться и другие символы).
Кроме того, в примерах будем справа от формул подстановки указывать их номера. Эти номера не входят в формулы, а нужны для ссылок на формулы при показе пошагового выполнения НАМ.