Пример 2 (перестановка символов)
А={a,b}. Преобразовать слово Р так, чтобы в его начале оказались все символы a, а в конце - все символы b.
Например: babba → aabbb
Решение.
Казалось бы, для решения этой задачи нужен сложный НАМ. Однако это не так, задача решается с помощью НАМ, содержащего всего одну формулу:
Пока в слове P справа хотя бы от одного символа b есть символ a, эта формула будет переносить a налево от этого b. Формула перестает работать, когда справа от b нет ни одного a, это и означает, что все a оказались слева от b. Например:
Алгоритм остановился на последнем слове, т.к. к нему уже неприменима наша формула.
Этот и предыдущий примеры показывают, что в НАМ, в отличие от машины Тьюринга, легко реализуются перестановки, вставки и удаления символов. Однако в НАМ возникает другая проблема: как зафиксировать символ (подслово), который должен быть обработан? Рассмотрим эту проблему на следующем примере.
Достарыңызбен бөлісу: |
