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

Пример 1. (перенос символа через слово) А={a,b}. Перенести в конец непустого слова Р его первый символ. Пустое слово не менять.

Например:

Решение.

Для решения этой задачи предлагается выполнить следующие действия.

1. Помечаем первый символ слова P спецзнаком *.

2. Заменяем * и этот символ на новый символ: a на A, b на B. Этим мы фактически вводим два новых спецзнака A и B, которые нужны, чтобы отличить первый символ слова от остальных символов при его переносе в конец слова.

3. Перегоняем новый символ A или B через все символы слова P в его конец. Такое перемещение реализуется аналогично перегону звёздочки - с помощью формул вида

4. Наконец, заменяем A или B в конце слова на прежний символ (A на a, B на b) и останавливаем алгоритм.

Все эти действия реализуются в виде следующего НАМ:

Здесь формулы (1) и (2) заменяют первый символ слова (вместе с *) на А или В. Формулы (3)—(6) перегоняют А и В в конец слова. Формулы (7) и (8) применяются только тогда, когда А и В окажутся в конце слова (когда за ними уже нет символов), и восстанавливают исходный вид первого символа. Формула (9) нужна на случай пустого входного слова. Формула же (10) ставит спецзнак * перед первым символом.

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

Другое решение

Отметим, что в этом НАМ можно уменьшить число формул, если не вводить новые символы A и B, а использовать вместо них пары *а и *b. Это позволит исключить из НАМ формулы (1) и (2), которые вводят символы A и B, и формулы (7) и (8), которые восстанавливают первый символ. Что же касается «перепрыгивания» этих пар через какой-то символ то оно реализуется формулами вида *а£а£*а и *b£a£*b. При этом никакой путаницы между первым символом слова и остальными символами не будет, т.к. только перед первым символом находится звёздочка.

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

Итак, возможен и следующий НАМ, решающий нашу задачу:

Пример 2 (использование нескольких спецзнаков) А={а,b}. Удвоить слово Р, т.е. приписать к P (слева или справа) его копию.

Например:

Решение.

Предлагается следующий план решения задачи:

1. Приписываем к концу слова Р символ =, справа от которого будем строить копию P.

2. Просматриваем по очереди все символы слова Р и, не уничтожая их, переносим копию каждого символа в конец.

3. Удаляем символ =, который отделял слово P от его копии, и останавливаем алгоритм.

Теперь уточним этот план.

Как приписать некоторый символ к концу слова, мы уже знаем: надо сначала приписать слева к слову какой-то спецзнак, скажем *, затем перегнать его направо через все символы слова и в конце, когда за * не окажется никакого символа, заменить на символ =:

Из предыдущего примера мы также знаем, как переносить символы слова в конец слова. Только теперь сами символы уничтожать уже не надо. Поэтому поступаем так: если надо скопировать символ a, то порождаем за ним новый символ A (заменяем a на aA), после чего этот символ A переставляем с каждым последующим символом (в том числе и с символом =), перенося тем самым A в конец слова, где и заменяем на a:

Аналогично копируются и символы b.

Главный вопрос здесь: как узнать, какой именно символ исходного слова мы только что скопировали и какой символ надо копировать следующим? Для этого используем стандартный приём со спецзнаком - будем помечать новым спецзнаком # тот символ, который должен копироваться следующим (вначале это первый символ входного слова):

Как только копия очередного символа окажется в конце, спецзнак # должен «запустить» процесс копирования следующего символа:

Когда справа от спецзнака # окажется символ =, это будет означать, что входное слово полностью скопировано. Осталось только уничтожить символы # и =, после чего остановиться.

Теперь отметим, что в НАМ, реализующем такое копирование, важен вза­имный порядок расположения формул ( ', A→a и B→b), которые переносят символы A и B в конец и там восстанавливают символы a и b, и формулами (#a^a#A и #b→b#B), которые «вводят в игру» символы A и B. Поскольку последняя пара формул должна срабатывать только после того, как символ A или B будет полностью перенесён в конец и заменён на a или b, то эта пара формулы должна располагаться в НАМ ниже всех первых формул.

И ещё один момент. В этом НАМ используются два спецзнака * и #, пер­вый из которых нужен для приписывания символа = справа к входному слову, а второй - для указания, какой символ слова должен копироваться следующим. Как ввести эти спецзнаки? Отметим, что использовать для этого две формулы→* и → #, нельзя, т.к. первая из них будет блокировать доступ ко второй. Оба этих спецзнака надо вводить сразу одной формулой→ #*. При этом надо учи­тывать, что формулы c* должны применяться самыми первыми, поэтому они должны располагаться в начале НАМ. Формулы же c #, A и B должны распо­лагаться ниже, чтобы они работали только после того, как исчезнет * и появится символ =.

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

Здесь формулы (1)-(3) «перегоняют» звёздочку в конец входного слова и заменяют её на символ =. Формулы (4)-(7) перегоняют символ A в конец слова, после чего заменяют на a. Формулы (8)—(11) делают то же самое с B и b. Формулы (12 и (13) «вводят в игру» символы A и B, соответствующие тому символу входного слова, который должен быть скопирован следующим. Формула (14) применяется только тогда, когда справа от # нет ни a, ни b, т.е. когда полностью просмотрено всё входное слово. И, наконец, формула (15) вводит сразу два спецзнака # и *.

Проверим данный алгоритм на двух входных словах - на пустом и на abb:

(т.е. получили <пустое слово><пустое слово>)

Другое решение

Приведём ещё одно решение задачи удвоения слова, в котором предлагается выполнить следующие действия.

1. Сначала за каждой (малой) буквой входного слова вставляем её двойник - соответствующую большую букву. Для этого приписываем слева к слову спецзнак *, а затем переносим его через каждую малую букву так, чтобы слева от него остались эта буква и её двойник. В конце слова заменяем * на новый спецзнак #, который нам ещё понадобится:

В получившемся слове переставляем малые и большие буквы так, чтобы слева оказались все малые буквы, а справа - все 2. большие, сохраняя при этом исходный взаимный порядок как среди малых, так и среди больших букв:

3. Как видно, справа мы получили копию входного слова, но записанную большими буквами. Осталось только заменить их на малые буквы. Вот здесь-то и понадобится спецзнак #: будем перемещать его влево через каждую большую букву с заменой её на малую. Когда слева от # уже не окажется большой буквы, надо уничтожить # и остановиться:

Все указанные действия описываются в виде следующего НАМ:

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

Замечания:

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

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

1. Перенести последний символ непустого слова P в начало слова.

2. . В непустом слове P переставить первый и последний символы.

3. . Если в непустом слове P совпадают первый и последний символы, то удалить оба этих символа, а иначе слово не менять.

4. . Определить, является ли слово P палиндромом (перевёртышем, симметричным словом). Ответ: слово a, если является, или пустое слово иначе.

5. . Пусть слово P имеет нечётную длину. Удалить из него средний символ.

6. Пусть слово P имеет следующий вид:

где - один из знаков , слева от которого указано n палочек, а

справа - m палочек. Реализовать соответствующую операцию в единичной сис­теме счисления (в качестве ответа выдать слово, указанное справа от стрелки):

7. A={ | }. Считая слово P записью числа в единичной системе, определить, является ли это число степенью 3 (1, 3, 9, 27, ...). Ответ: пустое слово, если является, или слово из одной палочки иначе.

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

9. A={ | }. Пусть слово P является записью числа 2n (n=0, 1, 2, ...) в единичной системе. Получить в этой же системе число n.

10. Пусть P имеет вид Q+R, где Q и R - непустые слова из символов 0, 1 и 2. Трактуя Q и R как записи троичных чисел (возможно, с незначащими нулями), выдать в качестве ответа запись суммы этих чисел в той же троичной системе.

11. Пусть P имеет вид Q-R, где Q и R - непустые слова из символов 0, 1 и 2. Трактуя Q и R как записи неотрицательных троичных чисел (возможно, с незначащими нулями) и считая, что Q>R, выдать в качестве ответа запись разности этих чисел в той же троичной системе.

12. Пусть P имеет вид Q=R, где Q и R - любые слова из символов α и b. Выдать ответ а, если слова Q и R одинаковы, и пустое слово иначе.

13. Пусть P имеет вид Q=R, где Q и R - непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.

14. Пусть P имеет вид Q>R, где Q и R - непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если число Q больше числа R, и слово 1 иначе.

15. A={( , )}. Определить, сбалансировано ли слово P по круглым скобкам. Ответ: Д (да) или Н (нет)

16. A={a,b}. Перевернуть слово P (например: abb →bba).