Приписать слева к слову p символ b

Приписать слева к слову p символ b

А=<0,1,2,3,4,5,6,7,8,9>. Пусть Р – непустое слово; значит, Р – это последовательность из десятичных цифр, т.е. запись неотрицательного целого числа в десятичной системе. Требуется получить на ленте запись числа, которое на 1 больше числа Р.

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

Перегнать автомат под последнюю цифру числа.

Если это цифра от 0 до 8, то заменить её цифрой на 1 больше и остановиться; например:

Если же это цифра 9, тогда заменить её на 0 и сдвинуть автомат к предыдущей цифре, после чего таким же способом увеличить на 1 ту предпоследнюю цифру; например:

Особый случай: в Р только девятки (например, 99). Тогда автомат будет сдвигаться влево, заменяя девятки на нули, и в конце концов окажется под пустой клеткой. В эту пустую клетку надо записать 1 и остановиться (ответом будет 100):

В виде программы для МТ эти действия описываются следующим образом:

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

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

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

1. A=. Приписать слева к слову P символ b (P → bP).

2. A=. Приписать справа к слову P символы bc (P → Pbc).

3. A=. Заменить на a каждый второй символ в слове P.

4. A=. Оставить в слове P только первый символ (пустое слово не менять).

5. A=. Оставить в слове P только последний символ (пустое слово не менять).

6. A=. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или пустое слово иначе.

7. A=. Определить, входит ли в слово P символ a. Ответ: слово из одного символа a (да, входит) или пустое слово (нет).

8. A=. Если в слово P не входит символ a, то заменить в P все символы b на с, иначе в качестве ответа выдать слово из одного символа a.

9. A=. Определить, является ли слово P идентификатором (непустым словом, начинающимся с буквы). Ответ: слово a (да) или пустое слово (нет).

10. A=. Определить, является ли слово P записью числа в двоичной системе счисления (непустым словом, состоящем только из цифр 0 и 1). Ответ: слово 1 (да) или слово 0.

11. A=<0,1>. Считая непустое слово P записью двоичного числа, удалить из него незначащие нули, если такие есть.

12. A=<0,1>. Для непустого слова P определить, является ли оно записью степени двойки (1, 2, 4, 8, …) в двоичной системе счисления. Ответ: слово 1 (является) или слово 0.

13. A=<0,1,2,3>. Считая непустое слово P записью числа в четверичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0.

14. A=<0,1>. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное учетверенному числу P (например: 101 → 10100).

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

16. A=. Если P – слово чётной длины (0, 2, 4, …), то выдать ответ a, иначе – пустое слово.

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

18. A=. Пусть P имеет нечётную длину. Оставить в P только средний символ.

19. A=. Если слово P имеет чётную длину, то оставить в нём только левую половину.

20. A=. Приписать слева к непустому слову P его первый символ.

21. A=. Для непустого слова P определить, входит ли в него ещё раз его первый символ. Ответ: a (да) или пустое слово.

22. A=. В непустом слове P поменять местами его первый и последний символы.

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

24. A=. Заменить в P каждое вхождение a на bb.

25. A=. Заменить в P каждое вхождение ab на c.

26. A=. Удвоить слово P (например: abb → abbabb).

27. A=. Удвоить каждый символ слова P (например: bab → bbaabb).

28. A=. Перевернуть слово P (например: abb → bba).

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

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

Читайте также:  Ошибка принтера 5800 canon

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

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

33. A=<0,1,2>. Считая непустое слово P записью числа в троичной системе счисления, получить запись этого числа в единичной системе.

34. Пусть слово P имеет вид || . | ⊗ || . |, где ⊗ – один из знаков +, –, ×, /, ÷, ↑ или ↓, слева от которого указано n палочек, а справа – m палочек. Реализовать соответствующую операцию в единичной системе счисления (в качестве ответа выдать слово, указанное справа от стрелки):

а) сложение: || . | + || . | →|| . |, справа от стрелки n + m палочек (n≥0, m≥0)

б) вычитание: || . | ‑ || . | →|| . |, справа от стрелки n ‑ m палочек (n≥m≥0)

в) умножение: || . | × || . | →|| . |, справа от стрелки m × n палочек (n≥0, m≥0)

г) деление нацело: || . | / || . | →|| . |, справа от стрелки k=n div m палочек (n≥0, m>0)

д) взятие остатка: || . | ÷ || . | →|| . |, справа от стрелки k=n mod m палочек (n≥0, m>0)

е) максимум: || . | ↑ || . | →|| . |, справа от стрелки k=max(n,m) палочек (n≥0, m≥0)

ж) минимум: || . | ↓ || . | →|| . |, справа от стрелки k=min(n,m) палочек (n≥0, m≥0)

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

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

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

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

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

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

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

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

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

44. A=. Если в P символов a больше, чем символов b, то выдать ответ a, если символов a меньше символов b, то выдать ответ b, а иначе в качестве ответа выдать пустое слово.

[1] Эмуля́ция (англ. emulation) — воспроизведение программными или аппаратными средствами либо их комбинацией работы других программ или устройств. Эмуляция позволяет выполнять компьютерную программу на платформе (компьютерной архитектуре и/или операционной системе), отличной, или в некоторых случаях идентичной той, для которой она была написана в оригинале. Эмуляцией также называют сам процесс этого выполнения. В отличие от симуляции, которая лишь воспроизводит поведение программы, при эмуляции ставится цель точного моделирования состояния имитируемой системы, для выполнения оригинального машинного кода.

[2]Если надо указать, что после выполнения некоторого такта МТ должна остановиться, то в третьей позиции этого такта будем писать знак «!». Например, такт b,L,! означает следующие действия: запись символа b в видимую клетку ленты, сдвиг влево и останов.

Нормальные алгоритмы Маркова

Пример 1 (замена символов)

А=<a,b,c,d>. В слове Р требуется заменить все вхождения подслова bb на ddd.

Например: abbcabbca → adddcabbca

Пример 2 (замена и удаление символов)

А=<a,b,c,d>. В слове Р требуется заменить первое вхождение подслова bb на ddd

Читайте также:  Ноутбук леново не загружается с флешки

и удалить все вхождения символа c.

Например: abbcabbca → adddabba

Но: abbcabbca → adddcabbca → adddcadddca → adddadddca → …

Но: abbcabbca → abbabbca → abbabba → adddabba → adddaddda

Пример 3 (перестановка символов)

А=<a,b>. Преобразовать слово Р так, чтобы в его начале оказались все символы

a, а в конце – все символы b.

Например: babba → aabbb

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

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

Но, bbaba -> bbba – удалили не первый символ

Но: bbaba → *bbaba → **bbaba → ***bbaba → …

Отсюда вытекает очень важное правило: если в НАМ есть формула с пустой левой частью (→β), то её место – только в самом конце НАМ.

Но: на пустом слове – будет зацикливание!

Пример 5 (вставка символа)

А=<a,b>. Вставить в начало любого слова символ а. Пустое слово не менять.

Например: babba → ababba

Пример 6 (перемещение спецзнака)

А=<a,b>. Требуется приписать символ a к концу слова Р.

Например: bbab → bbaba

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

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

bbab → *bbab → b*bab → bb*ab → bba*b → bbab*

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

Пример 7 (перенос символа через слово).

А=<a,b>. Перенести в конец непустого слова Р его первый символ. Пустое слово не менять.

Например: bbaba → babab

Проверка: bbaba → *bbaba → b*baba → ba*bba → bab*ba → baba*b babab

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

А=<0,1,2,3>. Пусть Р – непустое слово. Трактуя его как запись неотрицательного

целого числа в четверичной системе счисления, требуется получить запись это-

го же числа, но в двоичной системе.

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

Проверка: 0123 → *0123 → 00*123 → 0001*23 → 000110*3 → 00011011* -> 0001101

Пример 9 А=<0,1,2,3, 4, 5, 6, 7>. Пусть Р – непустое слово. Трактуя его как запись неотрицательного целого числа в восьмеричной системе счисления, требуется получить запись этого же числа, но в двоичной системе.

Например: 012345 → 000001010011100101

Задачи для самостоятельного решения

Замечание. Из предложенного списка заданий решить любые 10.

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

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

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

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

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

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

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

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

12 A=<a,b,c>. Преобразовать слово P так, чтобы сначала шли все символы a, затем – все символы b и в конце – все символы c.

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

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

16 A=<a,b,c>. Удвоить каждый символ в слове P (например: bacbbbaaccbb).

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

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

19 A=<a,b>. Перенести первый символ непустого слова P в конец слова.

20 A=<a,b>. В непустом слове P переставить первый и последний символы.

Написать программу на машине Тьюринга, прибавляющую число 2 к введенному числу.

Написать на машине Тьюринга программу, прибавляющую 3 к введенному числу.

Читайте также:  Группировать таблицу в ворде

Перенести первый символ непустого слова P в его конец. Алфавит : A=.

Если первый символ – это a, то надо перейти в состояние q2, в котором автомат бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где делается всё то же самое, только в конце записывается символ b. Если же первым был символ c, тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c.

Если первый и последний символы (непустого) слова P одинаковы, тогда это слово не менять, а иначе заменить его пустым словом. Алфавит: A =< a , b , c >.

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

Запомнить первый символ входного слова, не стирая его (перейти в состояние q 1 , если первый символ – a , q 3 , если первый символ – b и q 5 , если первый символ – c ).

Переместить автомат под последний символ и сравнить его с запомненным (в q 2 для a , в q 4 для b и в q 6 для c ). Если они равны, то больше ничего не делать.

В противном случае уничтожить всё входное слово ( q 7 ).

Удалить из слова P его второй символ, если такой есть. Алфавит: A =< a , b >.

Запомнить первый символ, стереть второй символ и установить на его месте первый.

Удалить из слова P первое вхождение символа a , если такое есть. Алфавит : A=.

Если первый символ слова – a , то стереть его и остановиться. Иначе сдвигаем символы слова на один символ вправо до тех пор, пока не найдем символ a .

Сдвиг символов осуществляется так: в очередной клетке записываем b (если в q 1 ) или c (если в q 2 ), переходим вправо и меняем состояние на q 1 (если в текущей клетке было записано b ) или на q 2 (если было записано c ), где осуществляется дальнейшая запись. Если в очередной клетке записано a или пробел, то записываем в нее запомненный символ и останавливаем программу.

Если P — непустое слово, то за его первым символом вставить символ a . Алфавит: A = < a , b , c >.

Аналогично заданию 5 запоминаем первый символ слова, меняем его на символ a , переходим на одну клетку влево и ставим там этот символ.

Вставить в слово P символ a за первым символом c , если такое есть. Алфавит: A = < a , b , c >.

Просматриваем слово до символа c или пустой клетки (в последнем случае останавливаем программу сразу). Затем, если c найден, запоминаем его и меняем на символ a , а далее запускаем цикл, который справа налево сдвигает символы слова, первоначально вставляя символ c перед a .

Удалить из P все вхождения символа a . A = < a , b , c >.

Вместо сдвига символов слова для закрытия образующихся дырок можно построить новое слово справа от предыдущего. Чтобы разграничить эти слова, отделим их некоторым вспомогательным символом, например знаком = , отличным от всех символов алфавита A .

Идем в конец слова и ставим знак = .

После этого возвращаемся к началу входного слова.

Теперь наша задача – перенести в цикле все символы входного слова, кроме a, вправо за знак = в формируемое выходное слово. Для этого анализируем первый символ входного слова. Если это a , тогда стираем его и переходим к следующему символу. Если же первый символ – это b или c , тогда стираем его и «бежим» вправо до первой пустой клетки, куда и записываем этот символ. Снова возвращаемся налево к тому символу, который стал первым во входном слове, и повторяем те же самые действия, но уже по отношению к этому символу.

Этот цикл завершается, когда при возврате налево мы увидим в качестве первого символа знак = . Это признак того, что мы полностью просмотрели входное слово и перенесли все его символы, отличные от a , в формируемое справа выходное слово. Надо этот знак стереть, сдвинуться вправо под выходное слово и остановиться.

Удвоить слово P , поставив между ним и его копией знак = . Алфавит: A = < a , b >.

Вначале записываем знак = за входным словом. Затем возвращаемся под первый символ входного слова.

Далее заменяем видимый символ a на двойник A (чтобы при возвращении к исходному слову знать, с какого символа продолжать копирование), «бежим» вправо до первой свободной клетки и записываем в неё символ a . После этого возвращаемся влево к клетке с двойником A , восстанавливаем прежний символ a и сдвигаемся вправо к следующему символу. Теперь аналогичным образом копируем второй символ (заменяем его на A , в конец дописываем a и т.д.) и все последующие символы входного слова.

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

Ссылка на основную публикацию
Принтер пишет барабан изношен что делать
Чтобы сбросить сообщение о замене, достаньте картридж.Снимите боковую крышку с платой. Параллельно резистору нужно припаять новый предохранитель (от 0,063 мА...
Почему яндекс картинки маленькие
В этом лайфхаке мы расскажем, почему не открываются картинки в браузере Яндекс и как включить их в настройках. Для начала...
Практическая работа по теме программное обеспечение компьютера
Содержание 12 урока "Системное программное обеспечение" Содержание 13 урока "Системы программирования и прикладное программное обеспечение" Практическая работа №4. "Программное обеспечение...
Приписать слева к слову p символ b
А=<0,1,2,3,4,5,6,7,8,9>. Пусть Р – непустое слово; значит, Р – это последовательность из десятичных цифр, т.е. запись неотрицательного целого числа в...
Adblock detector