Практическая работа №6: Использование спецзнака, фиксация спецзнаком заменяемого символа.

Пример 1 (использование спецзнака)

A={a,b}. Удалить из непустого слова Р его первый символ. Пустое слово не менять.

Решение.

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

Однако это неправильный алгоритм, в чём можно убедиться, применив его к слову bbaba:

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

Что делать? Надо как-то зафиксировать, пометить первый символ слова, например, поставив перед ним какой-либо знак, скажем *, отличный от символов алфавита слова. После этого уже можно с помощью формул вида заменить этот знак и первый символ слова на пусто и остановиться:

А как поставить * перед первым символом? Это реализуется формулой а* с пустой левой частью, которая, по определению, приписывает свою правую часть слева к слову.

Итого, получаем следующий НАМ:

:

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

1 1 1 1

bbaa → *bbaba → **bbaba → ***bbaba → ...

Как видно, этот алгоритм постоянно приписывает слева звёздочки. Почему? Напомним, что формула постановки с пустой левой частью применима всегда, поэтому наша формула (1) будет работать бесконечно, блокируя доступ к ос­тальным формулам. Отсюда вытекает очень важное правило: если в НАМ есть формула с пустой левой частью (ав), то её место - только в самом конце НАМ. Учтём это правило и перепишем наш НАМ:

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

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

Вот теперь мы, наконец-то, составили правильный алгоритм.

Прежде чем перейти к следующим задачам, обобщим тот приём со звёздочкой, который мы использовали в примере 1.

Пусть в обрабатываемое слово Р входит несколько раз подслово а :

и нам надо заменить одно из вхождений α на подслово β. Такая замена делается с помощью формулы α→β. Однако, если мы применим эту формулу к слову Р, то будет заменено первое вхождение α. А что делать, если надо заменить какое- другое вхождение α , скажем второе или последнее? Так вот, чтобы на β заменялось не первое вхождение α , а какое-то другое, это другое вхождение надо как-то выделить, пометить, для чего следует рядом с ним (слева или справа) поставить некоторый символ, скажем *, отличный от всех других символов, входящих в P:

Такой символ будем в дальнейшем называть спецзнаком. Его роль - вы­делить нужное вхождение α среди других, сделать его уникальным. Поскольку только около этого вхождения есть спецзнак, то надо использовать формулу * α→β, чтобы заменить на β именно это вхождение α , а не какое-то другое.

Этот приём со спецзнаком следует запомнить, т.к. в НАМ он используется очень часто.

Правда, остаётся ещё одна проблема: как спецзнак разместить рядом с нужным вхождением а ? Следующие примеры показывают, как это делается.

Пример 2 (фиксация спецзнаком заменяемого символа)

А={0,1,2,3}. Пусть Р - непустое слово. Трактуя его как запись неотрицательного целого числа в четверичной системе счисления, требуется получить запись это­го же числа, но в двоичной системе.

Например: 0123 → 00011011

Решение.

Как известно, для перевода числа из четверичной системы в двоичную надо каждую четверичную цифру заменить на пару соответствующих ей двоич­ных цифр: 0→ 00, 1 → 01, 2→ 10, 3→ 11. Такая замена, казалось бы, реализуется следующим НАМ:

Но этот алгоритм неправильный, в чём можно убедиться на входном слове 0123:

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

Как видно, слева от спецзнака всегда находится та часть числа, которая уже пере­ведена в двоичный вид, а справа - часть, которую ещё предстоит заменить. Поэтому никакой путаницы между четверичными и двоичными цифрами уже не будет.

Итак, спецзнак * сначала должен быть размещён слева от первой цифры четверичного числа, а затем он должен «перепрыгивать» через очередную чет­веричную цифру, оставляя слева от себя соответствующие ей двоичные цифры. В конце же, когда справа от * уже не окажется никакой цифры, спецзнак надо уничтожить и остановиться. Как приписать * слева к входному слову и как уничтожить спецзнак с остановом, мы уже знаем по предыдущему примеру, а вот «перепрыгивание» звёздочки реализуется с помощью формул вида *α→ βγ*, где α - четверичная цифра, а βγ - соответствующая ей пара двоичных цифр.

Итого, получаем следующий алгоритм перевода чисел из четверичной системы в двоичную:

Проверим этот НАМ на входном слове 0123:

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

Замечания:

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

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

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

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

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

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

5. A={a,b,c}. Удалить из непустого слова P его последний символ.

6. A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное учетверённому числу P (например: 101 ^ 10100).

7. A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное неполному частному от деления числа P на 2 (например: 1011 ^ 101).

8. A={a,b}. В слове P все символы a заменить на b, а все (прежние) символы b - на a.

9. A={a,b,c}. Удвоить каждый символ в слове P (например: bacb a bbaaccbb).

10. A={a,b}. Приписать справа к слову P столько палочек, сколько всего символов входит в P (например: babb a babb ||||).

11. A={a,b}. Пусть слово P имеет чётную длину (0, 2, 4, ...). Удалить правую половину этого слова. (Рекомендация: использовать решение предыдущей задачи.)

12. A={a,b}. Пусть длина слова P кратна 3. Удалить правую треть этого слова.

13. A={a,b}. Приписать справа к слову P столько палочек, со скольких подряд идущих символов a начинается это слово (например: aababa a aababa\ | ).

14. A={a,b,c}. Удалить из слова P второе вхождение символа a, если такое есть.

15. A={a,b,c}. Удалить из слова P третье вхождение символа a, если такое есть.

16. A={a,b,c}. Оставить в слове P только первое вхождение символа a, если такое есть.