Нормальные алгоритмы и Машина Тьюринга. Тесты

Нормальные алгоритмы и Машина Тьюринга. Тесты - 2020 год

Тест №1 “Алгоритмы” для группы ДКА – 101. Выполняется с 26.11.11 по 15.12.11.

Число попыток – 10.

Время на тест – 2 часа.

Проходной балл – 70.

Нестрогий контроль.

Оценивается в 9 – 15 баллов.

Тест состоит их двух частей: Нормальные алгоритмы и Машина Тьюринга.

Правильные ответы помечены – верно.

Нормальные алгоритмы

Задание 1. Дан алфавит{|, *, α, β}и последовательность команд, с помощью которой выполняется умножение натуральных чисел: β| → |β

α| → |βα

α → ˄

|* → *α

*| → *

* → ˄

Β → |

Какая последовательность получится при выполнении операции 2*3 на восьмом шаге?

1) |*|||βββα

2) |*|||βββ - верно

3) |β|βα|βββ

Задание 2.

Дан алфавит А=(^,a,b,c,z,x,v) входное слово R=abcvxazxa, и последовательность команд:

aàv

và^

càv

xà^

найти слово на 10 шаге алгоритма :

1. bvxzx

2. bzx - верно

3. bvxx

4. bvzx

Задание 3.Дан алфавит N=(^,a,b,c,d,α) входное словоH=dbbd, и последовательность команд:

bbàα

αàa

ddddàabcd

^adàda

aaàdd

^àα

найти слово на 10 шаге алгоритма :

1. abcd

2. ddbcd - верно

3. dabdc

Задание 4. Дан алфавит А={ |, -, ^}, входное слово ||||||||-|||||||||| и последовательность команд:

|-|à-;

-^à.^;

^-à.-

Какое слово получится после выполнения преобразований?

1. ||-;

2. ||;

3. -|| - верно

Задание 5. Используя алфавит А={X,Y,Z,A,α} и систему команд узнать как будет выглядеть слово XYZ на 14 шаге выполнения алгоритма.

Система команд:

Y ->XZ

XZ ->αX

X -> Z

Z ->α

αα -> Z

α ->· A

Ответ:

1) αA

2) A - верно

3) Aα

Задание 6.
Дан алфавит A={a₁, |, a₂, b₁, b₂}, и входное слово S=|a₁a_1.Также, дана система команд:

| à a₁ a₂a₁ a₁à b₁ a₂ b₂|a₂| à a₁ b₁a₂b₂ à | a₁ a₂|
b₁| à ||
| a₁ a₂| à a₂||

Как будет выглядеть слово на выходе?
1. a₁ a₂ a₁|| - верно
2. a₁ a₂ a₁ a₁
3. a₁ a₂ a₁ b₁|

Задание 7

Дан алфавит А={1,АО,2,F,3,S,4F5,7S,4A,10,7,5,4} и входное слово S=1 AO2F3S

Дана система команд:

1à2

2àAO

3à5

4F5à7

7SàA

4Aà10

Найти слово на девятом шаге алфавита:

1.44AOF3S

2.444F5S

3.44A - верно

Задание 8

Дан алфавит A={1,2,3,A,B,C}

Входное слово S=1A2B3C

Дана система команд:

1àC

A2àB

Bà1

C3àC

Как будет выглядеть слово на выходе?

1. C312AC

2. CCCC - верно

3. 3CCCC

Задание 9

Дан алфавит А={^,1,2,B,C,0,4} и дано и входное слово S=B12COB

Дана система команд:

Bà1

B1àC

11à2

22à4

CàB

BOàB

Каково будет конечное слово?

1.4BOB

2.4BB

3.44 - верно

Задание 10

Дан алфавит:
A={1,A,B,Z,8}
Входное слово:
R=A8B1Z
Система команд:
8 à AB
AAàZ
BBà1
11àZ
ZZZàAB

Ответ:
1)18
2)AB - верно
3)BA

Задание 11.

Дан алфавит {*,x,y,z,n,k,s}.
Вxодное слово: M=xyzskxnkx
Последовательность команд:
x-s
s-*
z-s
k-*
Найти слово на 9-ом шаге:
1.ksxynkx
2.ynk
3.yknk - верно
4.yzknk

Задание 12.

Дан алфавит {0, |, 1, ^}

Входное слово: 101

Последовательность команд:

|0 -> 0||

1 -> 0|

0 -> ^

Найти значение на 5-ом шаге:

1) 000||||| - верно

2) yzknk

3) ||00||

Задание 13.

Дан алфавит {a,b,c,α,β,||}

Входное слово: abc

Последовательность команд:

1) a->αα

2) α->||

3) c->β

4) b->β||

5) ||->a|

Найти значение на 5-ом шаге:

1) ||||β||β - верно

2) ||βa|α

3) ||β||α

Задание 14.

Дан алфавит {0,1,2,3,4,5,6,7,8,9}

Входное слово: 213759846

Последовательность команд:

1) 2->1

2) 3->55

3) 8->77

4) 9->22

5) 55->88

6) 444->1

7) 777->0

Найти значение на 8-ом шаге:

1)110775117746 - верно

2)11557597746

3)118875117746

Задание 15.

Дан алфавит {α,β,γ,Δ,ε}

Входное слово: Δεβαγ

Последовательность команд:

1) βα->αβ

2) γα->αγ

3) Δα->αΔ

4) εα->αε

5) γβ->βγ

6) Δβ->βΔ

7) Εβ->βε

8) Δγ->γΔ

9) Εγ->γε

10) εΔ->Δε

Найти значение после окончания выполнения алгоритма:

1) εΔγβα

2) γεΔαβ

3) αβγΔε - верно

Задание 16

Дан алфавит {ABCDE}

Список команд:

1) A->E

2)C->ABC

3)B->ECD

Найти значение на шестом шаге алгоритма

1)ABCDE

2)EBEBEBABCDE - верно

3)ABEBEBCDEA

4)EBEBCDEAEB

Задание 17.

Дан алфавит {a,b,c,1,2,3,^}

Входное слово: 1a2b3c

Последовательность команд:

1) 1->a

2) a->c

3) cc->b

4) b2->2b

5) bb->1

6) ^->a

Найти значение после 10 шага:

1) 2с3с

2) 223с

3) a2c3c - верно

Задание 18.

Дан алфавит {α,β,a,/ ,b,c,d}

Входное слово: abcd

Последовательность команд:

1) a->αα

2) β->α

3) b->//

4) α->β

5) ^->ββ

6) d->/

7) /->a

Найти значение после 5 шага:

1) ααβaα

2) βββ//cd - верно

3) ββββ

Машина Тьюринга

Задание 1. Дан набор правил для машины Тьюринга

A/Q	q₀	q₁	q₂
0	q₁αH	q₂0L	q₃0H
\|	q₀αL	q₀αL	q₂\|H
α	q₀αL	q₁αR	q₂\|L

На ленту записывается слово K=|. Какая последовательность получится на 5 шаге выполнения операций?

1)αα

2)αα0 - верно

3)α|0

Задание 2

Дан алфавит А={1,2,3,4,5,6,7,8,9,0,a₀}

a₀–пустой символ

q₀-состояние стопа

На ленту вводится слово 120800. Обзор числа начинается с крайнего правого элемента

Дан набор правил для МТ

q/a	0	1	2	3	4	5	6	7	8	9	a₀
q₁	q₂0 R	q₂1 R	q₂2 R	q₂3 R	q₂4 R	q₂5 R	q₂6 R	q₂7 R	q₂ 8 R	q₂ 9 R	q₂ a₀L
q₂	q₂9 L	q₀0 H	q₀1 H	q₀2 H	q₀1 H	q₀ 4 H	q₀5 H	q₀6 H	q₀7 H	q₀8H	q₀a₀H

Определить какое число будет выведено после завершения программы.

1) 120799 - верно

2) 120790

3) 2070

Задание 3. Дан набор правил для машины Тьюринга

A/Q	q₀	q₁	q₂
0	q₂αR	q₂0R	q₃0H
\|	q₀\|L	q₀αL	q₀0H
α	q₂\|L	q₁\|H	q₁αR

На ленту записывается слово H=|α|. Какая последовательность получится на 6 шаге выполнения операций?

1)|||

2)αααα - верно

3)α|α

Задание 4

Дан алфавит А={1,2,3,4,5,6,7,8,9,0,a₀}

a₀–пустой символ

q₀-состояние стопа

На ленту вводится слово 6661299. Обзор числа начинается с крайнего правого элемента

Дан набор правил для МТ

q/a	0	1	2	3	4	5	6	7	8	9	a₀
q₁	q₂0 R	q₂1 R	q₂2 R	q₂3 R	q₂4 R	q₂5 R	q₂6 R	q₂7 R	q₂ 8 R	q₂ 9 R	q₂ a₀L
q₂	q₂1 H	q₀2 H	q₀3 H	q₀4 H	q₀5 H	q₀ 6 H	q₀7 H	q₀8 H	q₀9 H	q₀0L	q₀a₀H

Определить какое число будет выведено после завершения программы.

1) 6661300 – верно

2) 666130

3) 666300

Задание 5. Дан набор правил для машины Тьюринга

Алфавит: {A,B,0}

0-пустое слово, q₀– начало, q₄– конец

Начальное слово AB

A/Q	q₀	q₁	q₂	q₃
A	q₀BH	q₁AR	q₃0H	q₃BR
B	q₁AL	q₂0R	q₃AH	q₄AL
0	q₁BR	q₂BR	q₃AH	q₄BL

Какая последовательность букв получится в конце выполнения?

1)BBB - верно

2)AB

3)BA

4)AAB

Задание 6. Дан набор правил для машины Тьюринга

A/Q	q₀	q₁	q₂
0	q₁αH	q₂\|L	q₃0H
\|	q₀αL	q₀αL	q₂αH
α	q₀0L	q₁αR	q₂\|L

На ленту записывается слово K=α|. Какая последовательность получится после 6 –ой команды выполнения операций?

1)α||

2)0||| - верно

3) ||||

Задание 7. Дан набор правил для машины Тьюринга

q0*→q0R q4a→q4aR

q01→q0R q4=→q4=R

q0×→q1×R q41→q41R

q11→q2aR q4*→q51R

q21→q21L q5*→q2*L

q2a→q2aL q6a→q61R

q2=→q2=L q6×→q7×R

q2×→q3×L q7a→q7aR

q31 → q4aR q71→q2aR

q3a→q3aL q7=→q8=L

q3*→q6*R q8a→q81L

q4×→q4×R q8×→q9H

Умножим с помощью МТ 3 на 2 в единичной системе. Какая последовательность получится после 19 –ой команды выполнения операций?

1)1111

2)11 - верно

3) 1111111

Задание 8

Дан алфавит А={1,2,3,4,5,6,7,8,9,0,a₀}

a₀–пустой символ

Q= {q0, q1, q2, q3}

q₀- завершающее состояние

На ленту вводится слово 525999.Обзор числа начинается с крайнего левого элемента

Дан набор правил для МТ

q/a	0	1	2	3	4	5	6	7	8	9	a₀
q₁	q₁0 R	q₁1 R	q₁2 R	q₁3 R	q₁4 R	q₁5 R	q₁6 R	q₁7 R	q₁ 8 R	q₁ 9 R	q₃ a₀L
q₂	q₀1 H	q₀2 H	q₀3 H	q₀4 H	q₀5 H	q₀ 6 H	q₀7 H	q₀8 H	q₀9 H	q₂0L	q₀a₀H
q₃	q₂0 L	q₂1 L	q₂2 L	q₂3 L	q₂4 L	q₂ 5 L	q₂6 L	q₂7 L	q₂8 L	q₂9L	q₂a₀L

Какое число будет выведено после завершения программы?

А. 525000

Б. 526000

В. 526009 -верно

Г. 526999

Задание 9

Дан алфавит {0, I, α}, где 0-пустое слово.

Q= {q0, q1, q2, q3}

q0- начальное состояние

q3-завершающее состояние

На ленту вводится слово |α|.

Дан набор правил для машины Тьюринга

q2 α R

q2 0 R

q3 0 H

q0 | L

q0 α L

q0 0 H

q2 I L

q1 | H

q0 α R

Определить шестую команду

А. q |L -> q1 α R

Б. q1 | H -> q3 0 H

В. q1 α R -> q0 α L - верно

Задание 10.

Машина Тьюринга

Дан алфавит: {X,Y,Z}

0-пустое слово

q₀– начало

q₄– конец

A/Q	q₀	q₁	q₂	q₃
X	q₀YH	q₁XR	q₃ZH	q₃YR
Y	q₁XL	q₂ZR	q₃XH	q₄XL
Z	q₁YR	q₂YR	q₃XH	q₄YL

На ленту вводиться слово: XY

Какая последовательность будет в конце исполнения?

1)XXY

2)YZ

3)YYY -верно

4)ZX

Задание 11. Дан набор правил для машины Тьюринга

Алфавит: A = {0,1},

0-пустое слово, q₀– начало, q₂– конец

Начальное слово q₁011…10

A/Q	q₀	q₁	q₂
1		0R q₂	1S q₀
2			1R q₂

Какая последовательность букв получится в конце выполнения?

M = q₁011…10

q₁0® q₂0R получаем 0q₂11…10

q₂1 ® q₂1R пока не получится 011…1q₂0

q₂0 ® q₀1, и машина остановится, ибо q₀ соответствует состоянию остановки.

1) q₂0 ® q₀1 - верно

2) q₂1 ® q₂1R

3) q₁0® q₂0R

Задание 12

Имеется машина Тьюринга с алфавитом A={1,2} и входным словом 1212. Определить что получится на выходе

q0 - стоп

q1 - начальное состояние

A/Q	q0	q1	q2
2		q₂1R	q₁1R
1		q₁1R	q₁1R

1) 1122

2) 12121

3) 1112 - верно

Задание 13

	ε	0	1
q₁	εRq₂	0Lq₁	1Lq₁
q₂	εHq_fin	0Lq₃	1Rq₂
q₃	εRq₄	1Lq₂	0Rq₃
q₄		εRq₂

На ленту записывается слово 1001110 Какая последовательность получится после окончания выполнения операций?

1) 1111 - верно

2) 101110

3) 0111001

Задание 14

	ε	0	1
q₁	εHq_fin	0Lq₂	1Lq₅
q₂		0Lq₁	0Rq₃
q₃		1Lq₄	1Lq₁
q₄		0Lq₁	1Lq₁
q₅		1Rq₆	1Lq₁
q₆			0Lq₃

На ленту записывается слово 011001 Какая последовательность получится после окончания выполнения операций?

1) 100110 - верно

2) 110100

3) 111000

Задание 15

Дан алфавит {1,2,3}

q_{0 –
начало}

q_{1 –
конец}

	q0	q₁	q₂
1		q₁_2R	q₀₁
2		q₁_1R	q₀₃
3		q₂_R	q₀₃

На ленту записывается слово 13211 Какая последовательность получится после окончания выполнения операций?

1) 21311 - верно

2) 32111

3) 32112