Скачиваний:
132
Добавлен:
15.06.2014
Размер:
82.43 Кб
Скачать

БГУИР

ФИТиУ

ОТЧЕТ

по дисциплине «Алгоритмы и алгоритмическая сложность»

лабораторная работа №1

«Машины Тьюринга»

Выполнили:

Арлынах

Проверила

Хаджинова Н. В.

Минск

2007

Практическое занятие «Машины Тьюринга»

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

Ход работы

В ходе работы мы закрепили знания по построению и работе машин Тьюринга, которые являются математическими моделями алгоритмов.

Было выполнено:

Задание 1. Построить таблицу машины Тьюринга, которая заменяет все единицы на нули, а все нули на единицы. Пример. Исходное число 111001. Результат – 000110.

Решение

1

ε

0

1

Q1

εUQfin

1LQ1

0LQ1

Задание 2. Построить таблицу машины Тьюринга, которая удаляет из числа все нули, например, число 1001110 преобразует к виду 1111. Эта задача уже сложнее и требует ввести в рассмотрение более двух состояний.

Решение

2

ε

0

1

Q1

εRQ2

0LQ1

1LQ1

Q2

εUQfin

0LQ3

1RQ2

Q3

εRQ4

1LQ2

0RQ3

Q4

εRQ2

Задание 3. Построить машину, имеющую два конечных состояния, условно обозначаемых как YES и NO. Машина должна завершить работу в состоянии YES, если число единиц в записи числа нечетное, и в состоянии NO – в противном случае.

Решение

3

ε

0

1

Q1

εUQN

0LQ1

1LQ2

Q2

εUQY

0LQ2

1LQ1

Задание 4. Построить машину, имеющую два конечных состояния, условно обозначаемых как YES и NO. Машина должна завершить работу в состоянии YES, если в записи числа имеется три подряд идущих единицы, и в состоянии NO – в противном случае.

Решение

4

ε

0

1

Q1

URQN

0LQ1

1LQ2

Q2

UUQN

0LQ1

1RQ3

Q3

URQN

0LQ1

UUQY

Задание 5. Построить машину Тьюринга, которая получает обратный порядок записи числа, например, исходное число 111001, результат 100111.

Решение

5

ε

0

1

Q1

εLQ22

εRQ2

εRQ11

Q2

0LQ3

Q3

εLQ4

Q4

εRQ5

0LQ4

1LQ4

Q5

εLQ6

εLQ14

Q6

0RQ7

Q7

εRQ8

Q8

εLQ1

0RQ8

1RQ8

Q9

εLQ10

Q10

εRQ11

0LQ10

1LQ10

Q11

1LQ9

εLQ18

εLQ12

Q12

1RQ13

Q13

εRQ8

Q14

0RQ15

Q15

εRQ16

Q16

εRQ17

0RQ16

1RQ16

Q17

εLQ1

1LQ17

Q18

1RQ19

Q19

εRQ20

Q20

εRQ21

0RQ20

1RQ20

Q21

0LQ21

εLQ22

0LQ8

Q22

εRQ24

0RQ21

1RQ23

Q23

1LQ23

εLQ22

Q24

εRQ25

Q25

εRQ26

0RQ25

1RQ25

Q26

εUQfin

0LQ27

0LQ28

Q27

0RQ27

εRQ26

Q28

1RQ28

εRQ26

Задание 6. Построить машину Тьюринга, которая меняет местами соседние два элемента попарно. Пример. Исходное число 011001 заменяется на 100110.

Решение

6

ε

0

1

Q1

εUQfin

0LQ2

1LQ5

Q2

0LQ1

0RQ3

Q3

1LQ4

1LQ1

Q4

0LQ1

1LQ1

Q5

1RQ6

1LQ1

Q6

0LQ3

Соседние файлы в папке Лаба 1 Машины Тьюринга