Дискретная математика. Элементы теории, задачи и упражнения. Часть 2. Булгакова И.Н. - 73 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

73
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Выяснить, применима ли МТ, задаваемая программой в алфавите
{
}
10,
0 1
1
q
2
0 qП
1
1 qП
2
q
3
0 qП
1
1 qЛ
3
q
0
0 qН
2
1 qЛ
к слову
P
:
1)
223
101
=
P ;
2)
33
101
=
P ;
3)
[
]
10110
2
=P .
Если применима, то найти результат применения МТ к слову
P
.
Ответ: В случаях
1), 3) — МТ применима,
2) — МТ не применима.
2. По заданной МТ и начальной конфигурации
1
K найти заключительную
конфигурацию.
MT
1
MT
2
0 1 0 1
1
q
0
0 qН
2
1 qП
1
q
0
0 qН
2
0 qП
2
q
0
1 qЛ
3
0 qП
2
q
1
0 qП
2
1 qЛ
3
q
1
1 qЛ
1
0 qП
1) 1011
3
1
2
1
qK
=
;
1)
5
11
11qK
=
;
2)
4
11
11qK
=
.
2) 011
3
11
qK
=
;
3)
4
11
110qK
=
.
Ответ: 1) 10101
0
22
q ; 2)
[
]
2
0
2
1010 q .
3. Построить МТ, которая применима ко всем словам в алфавите
{
}
b,a,
L
и делает следующее: любое слово
n
xxx
K
21
, где ax
i
=
или bx
i
=
,
)
n,i 1= , преобразует в слово
132
xxxx
n
K
.
Указание: В начальной конфигурации
¯
L
1
x
2
x
… …
n
x
L
1
q 
                          ЗАДАЧИ И УПРАЖНЕНИЯ

1. Выяснить, применима ли МТ, задаваемая программой в алфавите �0, 1�
                               0           1
                   q1       0 П q2      1 П q1
                   q2       0 П q3      1 Л q1
                   q3       0 Н q0      1 Л q2

к слову P :
                1) P � 13 0 2 12 ;
                2) P � 13 0 13 ;
              3) P � 10 �01� 1.
                                  2


Если применима, то найти результат применения МТ к слову P .
Ответ: В случаях
        1), 3) — МТ применима,
        2) — МТ не применима.

2. По заданной МТ и начальной конфигурации K 1 найти заключительную
   конфигурацию.
               MT1                                  MT2
               0        1                           0           1
   q1      0 Н q0    1 П q2              q1      0 Н q0      0 П q2
   q2      1 Л q0    0 П q3              q2      0 П q1      1 Л q2
   q3      1 Л q1    0 П q1            1) K 1 � 1 q1 1 0 1 ;
                                                 2     3


 1) K 1 � 1q1 1 ;
                5
                                       2) K 1 � 1q1 14 .
 2) K 1 � q1 13 01 ;
 3) K 1 � 10 q1 14 .
Ответ: 1) 12 0 2 1 q 0 0 1 ; 2) �10� 0 q 0 12 .
                                      2




3. Построить МТ, которая применима ко всем словам в алфавите �� , a , b�
   и делает следующее: любое слово x1 x 2 � x n , где x i � a или x i � b ,
   �i � 1, n� , преобразует в слово x x
                                  � x n x1 .
                                          2   3

   Указание: В начальной конфигурации

                    �
          �         x1       x2           …        …   xn   �
                    q1


                                              73

Страницы