Пример 1 (перемещение автомата, замена символов)





А={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={a,b,c}. Приписать слева к слову P символ b (P → bP).

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

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

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

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

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

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

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

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

10. A={a,b,0,1}. Определить, является ли слово 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={a,b,c}. Если P – слово чётной длины (0, 2, 4, …), то выдать ответ a, иначе – пустое слово.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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={a,b}. Если в P символов a больше, чем символов b, то выдать ответ a, если символов a меньше символов b, то выдать ответ b, а иначе в качестве ответа выдать пустое слово.

 

 


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

 

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





Читайте также:
Своеобразие родной литературы: Толстой Л.Н. «Два товарища». Приёмы создания характеров и ситуаций...
Образцы сочинений-рассуждений по русскому языку: Я думаю, что счастье – это чувство и состояние полного...
Пример художественного стиля речи: Жанры публицистического стиля имеют такие типы...
Новые русские слова в современном русском языке и их значения: Менсплейнинг – это когда мужчина что-то объясняет...

Рекомендуемые страницы:



Вам нужно быстро и легко написать вашу работу? Тогда вам сюда...

Поиск по сайту

©2015-2021 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-06-30 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту:

Мы поможем в написании ваших работ! Мы поможем в написании ваших работ! Мы поможем в написании ваших работ!
Обратная связь
0.02 с.