Практическая работа №5: Вставка и удаление символов, перестановка символов

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

Например:

Решение.

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

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

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

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

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

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

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

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

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

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

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

Пример 2 (перестановка символов) A={a,b}. Преобразовать слово Р так, чтобы в его начале оказались все символы a, а в конце - все символы b.

Например:

Решение.

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

Пока в слове P справа хотя бы от одного символа b есть символ a, эта формула будет переносить a налево от этого b. Формула перестает работать, когда справа от b нет ни одного a, это и означает, что все a оказались слева от b.

Например:

Алгоритм остановился на последнем слове, т.к. к нему уже неприменима наша формула.

Этот и предыдущий примеры показывают, что в НАМ, в отличие от машины Тьюринга, легко реализуются перестановки, вставки и удаления символов. Однако в НАМ возникает другая проблема: как зафиксировать символ (подслово), который должен быть обработан? Рассмотрим эту проблему на следующем занятии примере.

Задачи для решения

Замечания:

1.В задачах рассматриваются только целые неотрицательные числа, если не сказано иное.

2.Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек - должно быть выписано столько палочек, какова величина числа; например: 2→ | | , 5 →а | | | | | , 0 → <пустое слово>.

1. A={f,h,p}. В слове P заменить все парыph на f

2. A={f,h,p}. В слове P заменить на f только первую пару ph, если такая есть.

3. A={a,b,c}. Приписать слово bac слева к слову P.

4. A={a,b,c}. Заменить слово P на пустое слово, т.е. удалить из P все символы.

5. A={a,b,c}. Заменить любое входное слово на слово a.

6. Выписать НАМ, не меняющий входное слово (при любом алфавите A).

7. A={ | }. Считая слово P записью числа в единичной системе счисления, получить остаток от деления этого числа на 2, т.е. получить слово из одной палочки, если число нечётно, или пустое слово, если число чётно.

8. A={ | }. Считая слово P записью положительного числа в единичной системе счисления, уменьшить это число на 1.

9. A={ | }. Считая слово P записью числа в единичной системе счисления, увеличить это число на 2.

10. A={0,1,2}. Считая слово P записью числа в троичной системе счисления, получить остаток от деления этого числа на 2, т.е. получить слово 1, если число нечётно, или слово 0, если число чётно. (Замечание: в чётном троичном числе должно быть чётное количество цифр 1.)

11. A={a,b,c}. Определить, входит ли символ a в слово P. Ответ (выходное слово): слово a, если входит, или пустое слово, если не входит.

12. A={a,b}. Если в слово P входит больше символов a, чем символов b, то в качестве ответа выдать слово из одного символа a, если в P равное количество a и b, то в качестве ответа выдать пустое слово, а иначе выдать ответ b.

13. A={0,1,2,3}. Преобразовать слово P так, чтобы сначала шли все чётные цифры (0 и 2), а затем - все нечётные.

14. A={a,b,c}. Преобразовать слово P так, чтобы сначала шли все символы a, затем - все символы b и в конце - все символы c.

15. A={a,b,c}. Определить, из скольких различных символов составлено слово P; ответ получить в единичной системе счисления (например: acaac → | | ).

16. A={a,b,c}. В непустом слове P удвоить первый символ, т.е. приписать этот символ слева к P.

17. A={a,b,c}. За первым символом непустого слова P вставить символ c.