Практическая работа № 7: Перемещение спецзнака, смена спецзнака.

Пример 1. (перемещение спецзнака) A={a,b}. Требуется приписать символ a к концу слова Р.

Например:

Решение.

Прежде всего напомним, что формула →a приписывает символ a слева к слову P, а не справа. Чтобы приписать a справа, надо сначала пометить конец слова. Для этого воспользуемся спецзнаком, который поместим в конец P, а затем заменим его на a:

Но как поместить спецзнак в конец слова? Делается это так: сначала спецзнак * приписываем слева к слову P, а затем «перегоняем» звёздочку через все буквы слова:

А как сделать такой перегон? Нетрудно заметить, что «перепрыгивание» звё­здочки через какой-то символ ξ - это замена пары *ξ, на пару ξ *, которая реали­зуется формулой

С учётом всего сказанного получаем следующий НАМ:

Отметим, что при пустом входном слове этот НАМ сначала введёт звё­здочку, а затем тут же заменит её на символ a и остановится.

Пример 2. (смена спецзнака)

А={a,b}. В слове Рзаменить на aa последнее вхождение символа a, если такое есть.

Например:

Решение.

Удвоение символа a реализуется формулой a → αα. Но чтобы она применя­лась не к первому вхождению символа α, а к последнему, надо поставить, ска­жем, справа от последнего символа a спецзнак * и применить формулу a* → aa.

Теперь посмотрим, как поместить * рядом с последним вхождением сим­вола a. Поскольку последнее вхождение - это первое вхождение от конца, то предлагается сначала приписать * слева к слову P, затем перегнать * в конец слова (это мы уже умеем делать), а далее перегнать * справа налево через сим­волы b до ближайшего символа a. Кроме того, надо учесть, что в Р может и не быть символа a; поэтому, если звёздочка снова достигнет начала слова, её надо уничтожить и остановиться.

Реализуем эту идею в виде следующего НАМ:

Здесь формула (6) приписывает * слева к входному слову P, формулы (1) и (2) перегоняют * в конец P, после чего формула (3) перемещает * справа налево через все b в конце слова до ближайшего, т.е. последнего, символа a, и, наконец, формула (4) заменяет этот символ на aa и останавливает алгоритм. Формула же (5) нужна для входных слов, в которые не входит a.

Проверим этот алгоритм на входном слове bababb (двойная стрелка означает несколько шагов применения формул (1) и (2)):

Как видно, вместо того, чтобы двигаться справа влево до ближайшего символа a, звёздочка начала «прыгать» вокруг последнего символа слова. Почему? Дело в том, что формулы (1) и (2), перегоняющие * вправо, мешают формуле (3), перегоняющей * влево. Отметим, что перестановка этих формул не поможет, т.к. тогда * начнёт «плясать» вокруг первого символа входного слова. Что делать?

Ошибка произошла из-за того, что мы используем спецзнак * в двух разных целях - как для движения вправо, так и для движения влево. Так вот, чтобы этой ошибки не было, надо просто ввести еще один спецзнак, скажем #, распределив между этими спецзнаками обязанности: пусть * движется вправо, а # - влево. Появиться же спецзнак # должен тогда, когда * дойдет до конца слова, т.е. когда справа от * не окажется других символов. Такая замена

спецзнака «исключит из игры» все формулы со звёздочкой в левой части, поэтому они уже не будут мешать формулам со спецзнаком #. Если так и сделать, то получим следующий НАМ:

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

Если же во входное слово не входит символ a, тогда имеем:

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

Замечания:

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

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

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

2. A={a,b,c}. Из всех вхождений символа a в слово P оставить только послед­нее вхождение, если такое есть.

3. A={a,b,c}. Если слово P начинается с символа a, то заменить P на пустое слово, а иначе P не менять.

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

5. A={a,b,c}. Если буквы в непустом слове P не упорядочены по алфавиту, то заменить P на пустое слово, а иначе P не менять.

6. A={a,b,c}. Если P отлично от слова abaca, то заменить его на пустое слово.

7. A={0,1}. Считая непустое слово P записью двоичного числа, определить, является ли это число степенью 2 (1, 2, 4, ...). Ответ: слово 1, если является, или слово 0 иначе.

8. A={0,1,2,3}. Считая непустое слово P записью четверичного числа, про­верить, чётно оно или нет. Ответ: слово 0, если чётно, и слово 1 иначе.

9. A={0,1,2,3}. Считая непустое слово P записью четверичного числа, получить остаток от деления этого числа на 4.

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

11. A={0,1,2}. Считая непустое слово P записью троичного числа, увеличить это число на 1.

12. A={0,1,2}. Считая непустое слово P записью положительного троичного числа, уменьшить это число на 1.

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

14. . Считая непустое слово P записью числа в троичной системе, получить запись этого числа в единичной системе.

15. Определить, входит ли первый символ непустого слова P ещё раз в это слово. Ответ: слово a, если входит, или пустое слово иначе.

16. . Перенести первый символ непустого слова P в конец слова.