Дискретная математика. Элементы теории, задачи и упражнения. Часть 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