ВУЗ:
Составители:
Рубрика:
62
6. Построить композицию
21
TT машин Тьюринга
1
T и
2
T по паре состояний
(
10
q ,
21
q ) и найти результат применения композиции
21
TT к слову
P
.
1)
11
q
12
q
21
q
22
q
1
T :
0
Rq 0
12
Lq 1
10
,
2
T :
0
Rq 1
22
Lq 1
21
1
Lq 1
12
Rq 1
11
1
Rq 1
21
Eq 1
20
а) 101=
P
; б)
3
1=
P
.
2)
11
q
12
q
13
q
1
T :
0
Lq 0
10
Rq 0
13
Rq 0
11
1
Eq 1
12
Lq 1
13
Rq 0
11
21
q
22
q
2
T :
0
Rq 1
22
Rq 0
20
1
Lq 1
22
Lq 0
21
а) 011
2
=
P
; б)
4
1
=
P
.
3)
11
q
12
q
13
q
1
T :
0
Rq 0
12
Lq 0
13
Lq 1
10
1
Rq 1
11
Rq 1
13
-
21
q
22
q
23
q
2
T :
0
Lq 0
22
Rq 0
23
Rq 0
20
1
Lq 1
21
Rq 1
22
Lq 1
21
а)
3
1=
P
; б)
2
101=
P
.
7. Найти результат применения итерации машины
T
по паре состояний (
0
q ,
1
q ) к слову
P
(заключительными состояниями являются
0
q и
′
0
q ).
1)
1
q
2
q
3
q
4
q
5
q
T
: 0
Eq 0
0
Eq 0
4
Eq 0
5
Rq 1
3
Rq 1
0
1
Rq 0
2
Rq 0
2
Rq 0
1
- -
а)
3
1=
P
; б) 101=
P
.
2)
1
q
2
q
3
q
4
q
5
q
6
q
T
: 0
Rq 0
0
′
Rq 0
0
′
Rq 0
4
Lq 1
5
Lq 0
6
Rq 0
0
1
Rq 0
2
Rq 0
3
Rq 1
3
Rq 1
4
Lq 1
5
Lq 1
6
а)
2
1=
P
; б)
5
1=
P
.
6. Построить композицию T1T2 машин Тьюринга T1 и T2 по паре состояний
( q10 , q21 ) и найти результат применения композиции T1T2 к слову P .
1) q11 q12 q21 q22
T1 : 0 q12 0 R q101L , T2 : 0 q221R q211L
1 q121L q111R 1 q211R q201E
а) P = 101; б) P = 13 .
2) q11 q12 q13
T1 : 0 q10 0 L q13 0 R q11 0 R
1 q121E q131L q11 0 R
q21 q22
T2 : 0 q221R q20 0 R
1 q221L q21 0 L
а) P = 12 01 ; б) P = 14 .
3) q11 q12 q13
T1 : 0 q12 0 R q13 0 L q101L
1 q111R q131R -
q21 q22 q23
T2 : 0 q22 0 L q23 0 R q20 0 R
1 q211L q221R q211L
а) P = 13 ; б) P = 1012 .
7. Найти результат применения итерации машины T по паре состояний ( q0 ,
′
q1 ) к слову P (заключительными состояниями являются q0 и q0 ).
1)
q1 q2 q3 q4 q5
T : 0 q0 0 E q 4 0 E q5 0 E q31R q0 1R
1 q2 0 R q2 0 R q1 0 R - -
а) P = 13 ; б) P = 101.
2)
q1 q2 q3 q4 q5 q6
T: 0 q0′ 0 R q0′ 0 R q4 0 R q51L q6 0 L q0 0 R
1 q2 0 R q3 0 R q31R q 41R q51L q61L
а) P = 12 ; б) P = 15 .
62
