Математическая логика и теория алгоритмов. Сергиевская И.М. - 54 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

Составители: 

Рубрика: 

59
5)
⎪
⎪
⎩
⎪
⎪
⎨
⎧
Rqq
Eqq
Lqq
Rqq
T
11
10
11
00
:
22
02
21
11
; 0110
11
qK
=
.
6)
⎪
⎪
⎩
⎪
⎪
⎨
⎧
Lqq
Lqq
Lqq
Rqq
T
11
00
11
10
:
02
22
11
21
;
101
1
2
1
qK =
.
7)
⎪
⎪
⎩
⎪
⎪
⎨
⎧
Lqq
Eqq
Lqq
Rqq
T
01
10
11
00
:
12
02
11
21
;
3
1
2
1
011 qK = .
8)
⎪
⎩
⎪
⎨
⎧
Rqq
Rqq
Eqq
T
00
01
10
:
12
21
01
; 1011
1
2
1
qK = .
9)
⎪
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎪
⎨
⎧
Lqq
Rqq
Lqq
Rqq
Lqq
Eqq
T
01
10
01
10
11
00
:
13
13
32
02
21
01
; 11
1
5
1
qK = .
10)
⎪
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎪
⎨
⎧
Rqq
Lqq
Rqq
Lqq
Rqq
Eqq
T
01
10
01
10
11
00
:
13
13
32
02
21
01
; 011
3
11
qK = .
2. Выяснить, применима ли машина Тьюринга
T
к слову
P
. Если применима,
то записать результат )(
P
T
применения машины
T
к слову
P
. Предполагается, что в
начальный момент времени головка машины обозревает самую левую единицу
слова. 
         ⎧q1 0q1 0 R
         ⎪q 1q 1L
         ⎪ 1 2
5)   T :⎨                   ;   K1 = 10q1 01 .
             q
         ⎪ 2 0    0 q  1 E
         ⎪⎩q 2 1q 21R
          ⎧q1 0q 2 1R
          ⎪q 1q 1L
          ⎪ 1 1
6)   T :⎨                   ;   K1 = 12 0q11 .
             q
          ⎪ 2 2   0 q   0 L
          ⎪⎩q 2 1q0 1L
           ⎧q1 0q 2 0 R
           ⎪q 1q 1L
           ⎪ 1 1
7)   T :⎨                   ;   K1 = 12 q1 013 .
           ⎪  q 2 0 q 0 1E
           ⎪⎩q 2 1q1 0 L
            ⎧q1 0q0 1E
            ⎪
8)   T : ⎨q11q 2 0 R ;          K1 = 12 q1101.
            ⎪q 0 q 0 R
            ⎩ 2 1
       ⎧q1 0q0 0 E
       ⎪q 1q 1L
       ⎪ 1 2
       ⎪⎪q 2 0q0 1R
9) T : ⎨              ; K1 = 15 q11 .
        ⎪q 2 1q3 0 L
        ⎪q3 0q11R
        ⎪
        ⎪⎩q31q1 0 L
            ⎧q1 0q0 0 E
            ⎪q 1q 1R
            ⎪ 1 2
            ⎪⎪q 2 0q01L
10) T : ⎨                 ; K1 = q11301.
             ⎪q 2 1q3 0 R
             ⎪q3 0q11L
             ⎪
             ⎪⎩q31q1 0 R

      2. Выяснить, применима ли машина Тьюринга T к слову P . Если применима,
то записать результат T (P) применения машины T к слову P . Предполагается, что в
начальный момент времени головка машины обозревает самую левую единицу
слова.




                                                   59

Страницы