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

 

	B	1
q1	BRq1	1Rq2
q2	1Lq3	1Rq2
q3	BSq0	1Lq3

 

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

 

 

 

Задача 3.3

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

 

	B	a	b	c
q1		aRq2	BRq1	BRq1
q2	BLq3	BRq2	BRq2	BRq2
q3	BLq3	aSq0

 

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

 

 

Задача 3.4

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

 

	p	h	B
q1	BRq2	BRq3	BRq1
q2	pRq2	hRq2	pLq4
q3	pRq3	hRq3	hLq4
q4	pLq4	hLq4	BSq0

 

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

 

 

 

Класс 4

Задача 4.2:

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

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

 

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

 

 

 

Задача 4.3:

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

 

	B	1
q1	чSq0	BRq2
q2	нSqo	BRq1

 

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

 

 

 

 

 

 

 

Задача 4.4:

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

	p	h	f	B
q1	BSq0	BRq2	BRq3	BSq0
q2	hSq0	hRq2	hRq3	hSq0
q3	fSq0	Frq2	fRq3	fSq0

 

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

 

 

 

Задача 4.5:

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

 

	p	h	f	B
q1	pRq1	hRq1	pLq4	BSq0
q2	pLq2	pLq3	hLq4	pSq0
q3	hLq2	hLq3	hLq4	hSq0
q4	fLq2	fLq3	fLq4	fSq0

 

 

 

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

 

 

 

 

 

 

Класс  5.

Задача 5.2:

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

 

	1	0	B
q1	1q3R	0q2R	Bq0S
q2	0q4L	0q1R	Bq0S
q3	1q1R	1q4L	Bq0S
q4	0q5R	1q5R
q5	1q1R	0q1R

 

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

 

 

 

 

 

 

 

 

 

 

 

Задача 5.3:

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

	1	0	*	B
q1	*q2L	*q5L	*q1R	Bq7L
q2			*q2L	Bq3L
q3	1q3L	0q3L		1q4R
q4	1q4R	0q4R		Bq1R
q5			*q5L	Bq6L
q6	1q6L	0q6L		0q4R
q7			Bq7L	Bq8L
q8	1q8L	0q8L		Bq0S

 

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

 

 

 

Задача 5.4

 

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

 

 

	0	1	B
q1	Bq7R	Bq2R	Bq10R
q2	0q2R	1q2R	Bq3R
q3	0q3R	1q3|R	1q4R
q4			1q5L
q5	0q5L	1q5L	Bq6L
q6	0q6L	1q6L	Bq1R
q7	0q7R	1q7R	Bq8R
q8	0q8R	1q8R	0q9R
q9			0q5L
q10	0q0S	1q0S

 

 

 

 

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

 

 

 

 

Список литературы

 

1.  Пильщиков В.Н. Учебно-методическое  пособие. Машина

Тьюринга и алгоритмы Маркова. Решение задач / Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. - М.: МГУ, 2006. – 47 с.

 2.  Фалина И.Н. Тема "Машина Тьюринга" в школьном курсе информатики [Текст] : к изучению дисциплины / И.Н. Фалина // Информатика (ПС). - 2006. - №8. - С. 11-16