Машина Тьюринга. Контрольная работа 1. Машина тьюринга

• Название: Машина тьюринга
• Анкор: Машина Тьюринга
• Дата: 29.10.2021
• Размер: 89.91 Kb.
• Имя файла: Контрольная работа 1.docx
• Тип: Контрольная работа; #259270

Контрольная работа 1

МАШИНА ТЬЮРИНГА

Вариант №8

Цель работы: ознакомление с устройством и принципом работы машины Тьюринга.

2. Задание по работе.

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

Предполагается, что в начальном положении ГСЗ обозревает ячейку ленты с первым символом входной последовательности. В конечный момент времени ГСЗ должна обозревать ячейку с первым символом результата.

Проверку корректности работы спроектированной МТ необходимо провести в пакете JFLAP.

Вставка символа в слово.

На ленте расположено слово из букв a, b и c, например: abcbca. Если слово непустое, требуется после первого его символа вставить символ a (для приведенного примера результат: aabcbca).

Метод решения задачи. Очевидно, что между первым и вторым символами слова надо освободить клетку для нового символа a. Для этого надо заменить символ □, стоящий перед словом, на первый символ слова. При этом МТ читает первый символ и, для того, чтобы запомнить его, переходит в одно состояние, если это символ a, в другое – если b, в третье – если c. После копирования первого символа МТ заменяет первый символ исходного слова на символ a.

3. Разработка машины Тьюринга.

t=0,1:

□

a

b

c

b

c

a

□

Δ(q₀) ТК: q₀, a q₀, a, R

q₀, b q₀, b, R

q₀, c q₀, c, R
t=2:

□

a

b

c

b

c

a

□

Δ(q₀) TK: q₀, □ q₁, a, L

t=3:

□

a

b

c

b

c

a

□

Δ(q₁) TK: q₁, □ q₂, □, S

Сформируем таблицу

	q0	q1
a	q1, a, L
b	q1, b, L
c	q1, c, L
□	q1, a, S	q0, a, S

Проверим в jflap turing machine.



Вывод: В результате выполнения работы создана логическая функция машины Тьюринга для вставки символа в слово. Проверка работоспособности машины произведена в среде JFLAP. Изучено устройство и принцип работы машины Тьюринга.

4. Моделирование машины Тьюринга.