Лабораторная работа № 4

Группа а

Тема: Представление алгоритмов с помощью машины Тьюринга

Цель работы: Освоить методы анализа работы машин Тьюринга и их разработки для реализации заданного алгоритма.

Требования к выполнению работы

Задание состоит из двух частей:

1. Задана машина Тьюринга и ее начальная конфигурация. Написать алгоритм, состоящий из последовательности команд, реализуемых машиной, и конфигураций машины после выполнения каждой команды алгоритма.

2. Разработать машину Тьюринга, реализующую заданную программу. Для этого:

   1. Дать словесное описание алгоритма;

   2. Определить внешний алфавит А, если он не задан (набор входных символов);

   3. Определить внутренний алфавит Q (перечень состояний);

   4. Определить заключительное состояние машины;

   5. Составить программу машины в виде таблицы переходов или последовательности команд;

   6. Проверить функционирование машины, написав алгоритм обработки различных входных последовательностей;

   7. Проверить функционирование машины для тех же входных последовательностей с помощью эмулятора машины Тьюринга.

---

Варианты заданий.

Часть 1

1. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇}и со следующей функциональной программой:

Q A	q1	q2	q3	q4	q5	q6	q7
а0	q4а0П	q6а0 П	q6а0 П	q01С	q4 а0 П	q0а0С	q6а0 П
1	q21Л	q31Л	q11Л	q5а0С	q5а0С	q7а0 С	q7а0 С

Начальная конфигурация: а) q₁11111; б) q₁111.

2. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1, *}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q₃,}и со следующей функциональной программой: q₁ 1q₂а₀Л, q₁*q₀ а₀С, q₂а₀q₃ 1П, q₂1q₂1Л, q₂*q₂*Л, q₃а₀q₁ а₀Л, q₃1q₃1П, q₃*q₃*П.

Начальная конфигурация: q₁11*111.

3. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1, *}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q_3, q₄} и со следующей функциональной программой:

Q A	q1	q2	q3	q4
а0	q1а0П	q3 а0П	q3а0Л	q1а0Л
1	q3а0Л	q21Л	q4 а0П	q41П
*	q0 а0С	q3*Л	-	q4*П

Начальная конфигурация: а) q₁111*11; б) q₁11*11.

4. Дана машина Тьюринга с внешним алфавитом А = {s₀, 1, , }, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q_3, q₄} и со следующей функциональной программой:

Q A	q1	q2	q3	q4
s0	q4s0П	q3s0Л	q1s0П	q0s0Л
1	q2С	q1С	q11П	q11Л
	q1Л	q2П	q31Л	q4 s0П
	q1Л	q2П	q3s0Л	q41П

Начальная конфигурация: q₁111*11

5. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇}и со следующей функциональной программой: q₁ а₀q₄а₀П, q₁1 q₂1Л, q₂а₀q₆ а₀ П, q₂1q₃1Л, q₃а₀q₆а₀ П, q₄ а₀ q₀1С, q₅ а₀q₄ а₀ П, q₆а₀q₀а₀С, q₇а₀q₆а₀ П, q₃1q₁1Л, q₄1q₅а₀С, q₅1q₅а₀С, q₆ 1q₇а₀ С, q₇1q₇а₀ С

Начальная конфигурация: а) q₁1а₀111 а₀ а₀1111.

6. Дана машина Тьюринга с внешним алфавитом А = {s₀, 1}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q_3, q_4, q₅, q₆, q₇, q_8, q_9, q₁₀} и со следующей функциональной программой:

Q A	q1	q2	q3	q4	q5	q6	q7	q8	q9	Q10
s0	q4s0П	q6s0П	q8s0П	q0s0С	q4s0П	q01С	q6s0П	q101С	q8s0П	q01С
1	q21Л	q31С	q11Л	q5s0С		q7s0С		q9s0С		q101П

Начальная конфигурация: а) q₁11111; б) q₁1111.

7. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1, *}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q₃} и со следующей функциональной программой:

Q A	q1	q2	q3
а0	-	q31П	q1а0Л
1	q2 а0Л	q21Л	q31П
*	q0 а0С	q2*Л	q3*П

---

Начальная конфигурация: а) q₁111*111; б) q₁1*11.

8. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1, *}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q₃,, q₄}и со следующей функциональной программой: q₁а₀q₂а₀П, q₁1q₃а₀Л, q₁*q₀ а₀С, q₂а₀q₃ а₀П, q₂1q₂1Л, q₂*q₃*Л, q₃а₀q₃а₀Л, q₃1q₄а₀П, q₄а₀q₁ а₀Л, q₄1q₄1П, q₄*q₄*П

Начальная конфигурация: 1111*11*1*11

9. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q₃} и со следующей функциональной программой:

Q A	q1	q2	q3
а0	q2а0П	q2 а0П	q0а0С
1	q11П	q31П	q31П

Начальная конфигурация: q111а₀а₀1.

10. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q₃} и со следующей функциональной программой:

Q A	q1	q2	q3
а0	q1а0П	q3а0Л	q0а0С
1	q21П	q1а0П	q21Л

Начальная конфигурация: q₁1111а₀1.

11. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1, *}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q₃,, q₄}и со следующей функциональной программой: q₁s₀q₄s₀П, q₁1q₂аС, q₁q₁аЛ, q₁q₂Л, q₂s₀q₃s₀Л, q₂1q₁С, q₂q₂аП, q₂q₂П, q₃s₀q₁s₀Л, q₃1q₁1П, q₃q₃1Л, q₃q₃s₀Л, q₄s₀q₀s₀Л, q₄1q₁1Л, q₄q₄s₀П, q₄q₄1П.

Начальная конфигурация: а) 1q₁111 , б) q₁111.

12. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q_3, q₄} и со следующей функциональной программой:

Q A	q1	q2	q3	q4
а0	q2а0П	q3а0Л	q11Л	q0а0С
1	q21П	q4а0П	q01С	q2а0П

Начальная конфигурация: q₁111а₀1а₀1.

13. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1}, алфавитом внутренних состояний Q = {q₀, q₁} и со следующей функциональной программой:

Q A	q0	q1
а0		q01П
1	q2а0Л	q11П

Начальная конфигурация: q₁1а₀1 q₁1а₀а₀11.

14. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1}, алфавитом внутренних состояний Q = { q₀, q₁, q₂, q_3, q_4, q₅, q₆, q₇, q_8, q_9, q₁₀} и со следующей функциональной программой: q₁s₀q₄s₀П, q₁1q₂1Л, q₂s₀q₆s₀П, q₂1q₃1С, q₃s₀q₈s₀П, q₃1q₁1Л, q₄s₀q₀s₀П, q₄1q₅ s₀С,. q₅s₀q₄s₀П, q₆s₀q₀1С, q₆1q₇s₀С, q₇s₀q₆s₀П, q₈s₀q₁₀1С, q₈1q₀s₀С, q₉s₀q₈s₀П, q₁₀s₀q₀1С, q₁₀1q₁₀1П

Начальная конфигурация: q₁111 , б) 1111111111.

15. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q₃,}и со следующей функциональной программой: q₁1q₁1П, q₁а₀q₂а₀П, q₂а₀q₂а₀П, q₂1q₃1П, q₃а₀q₀а₀С, q₃1q₃1П

Начальная конфигурация: q₁1а₀1а₀1а₀1.

16. Дана машина Тьюринга с внешним алфавитом А = {s₀, a, b, c}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q_3, q₄} и со следующей функциональной программой:

Q A	q1	q2	q3	q4
s0	q1s0Л	q0аC	q0bC	q0cC
a	q2s0Л	q2aЛ	q3aЛ	q4aЛ
b	q3s0Л	q2bЛ	q3bЛ	q4bЛ
c	q4s0Л	q2cЛ	q3cЛ	q4cЛ

---

Начальная конфигурация: q₁aabcbbc.

17. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q₃,}и со следующей функциональной программой: q₁а₀q₁а₀П, q₁1q₂1П, q₂а₀q₃а₀Л, q₂1q₁ а₀П, q₃а₀q₀а₀С, q₃1q₂1Л

Начальная конфигурация: q₁1а₀1а₀1а₀1.

18. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1}, алфавитом внутренних состояний Q = {q₀, q₁}и со следующей функциональной программой: q₁а₀q₀1Л, q₁1q₁1П, q₀1q₂а₀Л

Начальная конфигурация: 11q₁а₀1111.

19. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q₃,, q₄}и со следующей функциональной программой: q₁а₀q₂а₀П, q₁1q₂1П, q₂а₀q₃ а₀Л, q₂1q₄а₀П, q₃а₀q₁1Л, q₃1q₀а₀С, q₄а₀q₀а₀С, q₄1q₂а₀П.

Начальная конфигурация: q₁1а₀11а₀111а₀11.

20. Дана машина Тьюринга с внешним алфавитом А = {s₀, a, b, c}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q_3, q₄} и со следующей функциональной программой: q₁s₀q₁s₀Л, q₁aq₂s₀Л, q₁bq₃s₀Л, q₁cq₄s₀Л, q₂s₀q₀aC, q₂aq₂aЛ, q₂bq₂bЛ, q₂сq₂сЛ, q₃s₀q₀bC, q₃aq₃aЛ, q₃bq₃bЛ, q₃сq₃сЛ, q₄s₀q₀cC, q₄aq₄aЛ, q₄bq₄bЛ, q₄сq₄сЛ.

Начальная конфигурация: q₁aababcabb.

21. Дана машина Тьюринга с внешним алфавитом А = {а₀, 1, *}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q₃} и со следующей функциональной программой:

Q A	q1	q2	q3
а0	-	q31П	q1а0Л
1	q2 а0Л	q21Л	q31П
*	q0 а0С	q2*Л	q3*П

Начальная конфигурация: а) q₁11*111*1*1.

---

Часть 2

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

2. Дана конечная совокупность единиц, вписанных в ячейки, взятые подряд без пропусков. Постройте функциональную схему такой машины Тьюринга, которая записывала бы в десятичной системе число этих единиц, т. е. пересчитывала бы набор единиц (дешифратор).

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

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

5. На ленте записано выражение x+y, где x и y – числа в двоичной системе счисления. Получить результат операции.

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

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

8. Реализовать функцию f=x - 4.

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

10. Определить, имеется ли во входном тексте слово «каракатица».

11. Используя программу счетчика, вычитающего единицу из десятичной записи натурального числа, составьте программу машины Тьюринга, которая бы по десятичной записи числа п выписывала бы на ленту n палочек (шифратор).

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

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

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

15. Во входном тексте подсчитать количество слов.

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

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

18. A={f, r, 2, 5, c, d}. Определить, является ли слово P записью числа в шестнадцатеричной системе счисления.

19. На ленту подряд вписаны два конечных набора из m и n единиц, разделенные звездочкой. Причем в левом наборе единиц не меньше, чем в правом (m > n). Составьте программу машины Тьюринга, которая в левом наборе оставляла бы ровно столько единиц, на сколько единиц в левом наборе больше, чем в правом, а все остальные единицы стирала бы (вычитание единиц).

20. Постройте машину Тьюринга, осуществляющую перевод слова 001x10 в слово 01x00, где 1х = 1...1 (х единиц). Причем в начальном положении машина должна находиться в состоянии q₁ и обозревать правую ячейку, эту же ячейку она должна обозревать и в момент остановки.

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

---

Смотрите также файлы

• Лабораторная работа 3. Рекурсия.doc

• Лабораторная работа 2. Автоматы.doc

• Лабораторная работа. Системы и их виды.doc

• Лабораторная базы данных.doc

• Лабораторные Поисковые системы Расширенный поиск.docx