Детерминированные машины Тьюринга

В состоянии q2 пропускает все единички, при этом уже двигается влево. Когда видит пустой символ, записывает в эту ячейку единицу и переходит в состояние, при этом двигается влево.

В состоянии q3 когда машина видит пустой символ, останавливается и завершает свою работу.

Табличное представление решения задачи:

 

	B	1
q1	BLq2	1Rq1
q2	1Lq3	1Lq2
q3	BSq0	1Lq3

 

 

 

 

 

 

Решение задачи, представленное в виде блок-схемы:

Задача 3.2:

Даны два числа a и b, представленные в унарной системе счисления. Разработать программу для машины Тьюринга, которая найдет сумму этих чисел.

Машина начинает работу, обозревая самый левый непустой символ.

В момент остановки машины текущим символом должен быть самый левый непустой символ. [1]

Задача 3.3:

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

Машина начинает свою работу, обозревая самый левый непустой символ. [2]

Задача 3.4:

Дан алфавит А ={p,h}. Построить машину Тьюринга, которая перенесет первый символ непустого слова в его конец.

Машина начинает работу, обозревая самый левый непустой символ. [2]

Раздел 4. Класс 4.

Задача 4.1:

На ленте машины Тьюринга содержится последовательность символов. Напишите программу для машины Тьюринга, которая каждый второй символ «+» заменит на «-».

Машина начинает свою работу, обозревая самый левый непустой символ.

В момент остановки машины текущим символом должен быть самый левый непустой символ. [1]

Решение:

Разберем подробно решение данной задачи.

В состоянии q1 машина пробегает все символы «+», двигается при этом вправо. Когда машина видит пустую ячейку, переходит в состояние q2 и двигается влево.

В состоянии q2 машина  видит символ «+» оставляет его и переходит в состояние  q3, при этом двигается влево.

В состоянии q3 машина видит символ «+», то заменяет на «-», переходя в состояние q2. Получается, что каждый второй символ «+» будет заменен на

«-». Когда машина встретит пустую ячейку, машина завершит работу.

Табличное представление решения задачи:

	B	+
q1	BLq2	+Rq1
q2	BSq0	+Lq3
q3	BSq0	-Lq2

 

 

 

 

 

 

Решение задачи, представленное в виде блок-схемы:

 

Задача 4.2:

На ленте машины Тьюринга записано  число а в двоичной системе счисления. Прибавить к этому числу 1.

Машина начинает свою работу, обозревая самый левый непустой символ. [2]

 

 

Задача 4.3:

Построить машину Тьюринга, проверяющую число на четность. Если число четное, то на ленте должно остаться «ч», в противном случае «н». Число записано в унарной системе счисления.

Машина начинает работу, обозревая самый левый непустой символ. [2]

 

 

 

 

Задача 4.4:

Дан алфавит А={p,h,f}. На ленте записано слово. Удалить из слова первое вхождение символа Р, если такой есть.

Машина начинает свою работу, обозревая самый левый непустой символ. [2]

 

Задача 4.5:

Дан алфавит A={p,h,f}. На ленте машины Тьюринга содержится последовательность символов. Вставить p за первым вхождение символа f.

Машина начинает свою работу, обозревая самый левый непустой символ. [2]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Раздел 5. Класс 5

Задача 5.1:

Дана строка из символов a и b. Разработать машину Тьюринга, которая переместит все символы «а» в левую, а символы «b» - в правую части строки.

Машина начинает свою работу, обозревая самый левый непустой символ. [2]

Решение:

Разберем подробно решение данной задачи.

В состоянии q1 машина пропускает символы а, при этом двигается вправо, находясь в этом же состоянии. Когда машина видит символ b, оставляет символ b и переходит в состояние q2.

В состоянии q2 машина видит символ а и заменяет его на символ b, переходя в состояние q3, при этом двигается влево. Когда машина видит символ b, оставляет символ b, оставаясь в этом же состоянии.

В состоянии q3 машина пропускает символы а, переходя в следующее состояние, при этом двигается вправо. Если видит символ b, пропускает его, переходя в состояние q3, при этом двигается влево.

В состоянии q4 машина видит символ b, заменяет на символ а, переходя в состояние q1, при этом двигается вправо.

В состоянии q1 когда видит пустую ячейку, машина завершает свою работу.

Табличное представление решения задачи:

 

	B	a	b
q1	BSq0	aRq1	bRq2
q2	BSq0	bLq3	bRq2
q3	BRq4	aRq4	bLq3
q4			аRq1

 

 

Решение задачи, представленное в виде блок-схемы:

 

 

 

 

 

 

 

 

 

Задача 5.2:

Дана строка из символов 0 и 1. Разработать машину Тьюринга, которая поменяет местами пары соседних элемента.

Например, 101010 ->010101

Машина начинает свою работу, обозревая самый левый непустой символ. [2]

 

Задача 5.3:

Дан алфавит  А={0, 1, B, *}. На ленте записана последовательность, состоящая из 0, 1. Используя вспомогательный элемент *, записать эту последовательность в обратном порядке.

Например, 1100->0011.

Машина начинает свою работу, обозревая самый левый непустой символ.

 

Задача 5.4:

На ленте записана последовательность, состоящая из 0, 1. Написать программу, которая удвоит каждый символ последовательности.

Например, 101->110011.

Машина начинает свою работу, обозревая самый левый непустой символ. [2]

 

 

 

 

 

 

 

 

 

Варианты решения

Класс 1

Задача  1.2:

Табличное представление решения задачи:

	a	b	B
q1	aLq2	bLq3	BRq1
q2			aSq0
q3			bsq0

 

Решение задачи, представленное в блок схеме:

 

 

 

 

 

Задача 1.3:

Табличное представление решения задачи:

	1	2	B
q1	1Lq1	2Lq2	BSq0
q2			*Lq3
q3			*Sq0

 

 

Решение задачи, представленное в виде блок-схемы:

 

 

 

 

Задача 1.4

Табличное представление решения задачи:

	d	B
q1	dLq1	oLq2
q2		kSq0

 

Решение задачи, представленное в виде блок-схемы:

 

 

 

 

 

 

 

 

Задача 1.5

Табличное представление решения задачи:

	p	h	B
q1	BRq2	BRq3	BSq0
q2	pSq0	Psq0	pSq0
q3	hSq0	hSq0	hSq0

 

Решение задачи, представленное в виде блок-схемы:

 

 

 

Класс 2

Задача  2.2

Табличное представление решения задачи:

 

 

	a	b	B
q1	bRq1	bRq1	BSq0

 

Решение задачи, представленное в виде блок-схемы:

 

 

 

 

 

 

 

 

Задача 2.3:

Табличное представление решение задачи:

	a	b	c	B
q1	BRq1	BRq1	BRq1	BSq0

 

Решение задачи, представленное в виде блок-схемы:

 

 

 

 

 

 

 

 

 

 

 

Задача  2.4

 

Табличное представление решение задачи:

 

	1	B
q1	1Rq1	1Sq0

 

 

Решение задачи, представленное в виде  блок-схемы:

 

 

 

 

 

 

 

 

Задача  2.5

Табличное представление решение задачи:

 

	В	1
q1	ВRq1	0Rq2
q2	1Sq0	1Rq2

 

Решение задачи, представленное в виде блок-схемы:

 

 

 

 

Задача  2.6

Табличное представление решение задачи:

 

	0	1	B
q1	0Rq1	1Rq1	BLq2
q2	чLq3	нLq3	BLq2
q3	BLq3	BLq3	BSq0

 

Решение задачи, представленное в виде блок-схемы:

 

 

 

 

 

Класс 3

Задача 3.2:

Табличное представление решение задачи: