Решение.

Прежде всего, отметим, что в НАМ, в отличие от машины Тьюринга, легко реализуются вставки и удаления символов. Вставка новых символов в слово – это замена некоторого подслова на подслово с бóльшим числом символов; например, с помощью формулы bbddd два символа будут заменены на три символа. При этом не надо заботиться о том, чтобы предварительно освободить место для дополнительных символов, в НАМ слово раздвигается автоматически. Удаление же символов – это замена некоторого подслова на подслово с меньшим числом символов; например, удаление символа c реализуется формулой c(с пустой правой частью). При этом никаких пустых позиций внутри слова не появляется, сжатие слова в НАМ происходит автоматически.

С учётом сказанного нашу задачу должен, казалось бы, решать такой НАМ:

(14.2)

Однако это не так. Проверим этот НАМ на входном слове abbcabbca (над стрелками указаны номера применённых формул, а в словах слева от стрелок подчёркнуты для наглядности те части, к которым были применены эти формулы):

Как видно, заменив первое вхождение bb на ddd, этот НАМ не перешёл сразу к удалению символов c, а стал заменять и другие вхождения bb. Почему? Напомним, что на каждом шаге работы НАМ формулы подстановки всегда просматриваются сверху вниз начиная с первой из них. Поэтому, пока применима первая формула, она и будет применяться, блокируя доступ к остальным формулам. Этот означает, что в НАМ важен порядок перечисления формул подстановки.

Учтём это и переставим наши две формулы:

(14.3)

Проверим этот новый алгоритм на том же входном слове:

Итак, НАМ сначала удалил все символы c и только затем заменил первое вхождение bb на ddd. Однако НАМ на этом не остановился и стал заменять остальные вхождения bb. Почему? Дело в том, что, пока применима хотя бы одна формула, НАМ продолжает свою работу. Но нам этого не надо, поэтому мы должны принудительно остановить НАМ после того, как он заменил первое вхождение bb.

Вот для этого и нужны заключительные формулы подстановки, после применения которых НАМ останавливается. Следовательно, в нашем алгоритме обычную формулу bb→ddd надо заменить на заключительную формулу bbddd:

(14.4)

Вот теперь наш алгоритм будет работать правильно:

Слово, которое получилось после применения заключительной формулы (2) из (14.4), является выходным словом, т. е. результатом применения НАМ к заданному входному слову.

Проверим наш НАМ ещё и на входном слове, в которое не входит bb:

К последнему слову (dab) неприменима ни одна формула, поэтому, согласно определению НАМ, алгоритм останавливается и это слово объявляется выходным.