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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
128
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Выяснить, применима ли МТ, задаваемая программой в алфавите
{
}
10 ,
0 1
1
q
2
0qП
1
1qП
2
q
3
0qП
1
1qЛ
3
q
0
0qН
2
1qЛ
к слову
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
11 qK = ;
2)
4
11
11 qK = .
2) 011
3
11
qK = ;
3)
4
11
110qK = .
Ответ : 1)
10101
0
22
q
; 2)
[
]
2
0
2
1010 q
.
3. Построить МТ, которая применима ко всем словам в алфавите
{
}
b,a,
Λ
и делает следующее: любое слово
n
xxx K
21
, где ax
i
=
или bx
i
=
,
(
)
n,i 1 =
, преобразует в слово
132
xxxx
n
K .
Указание: В начальной конфигурации
Λ
1
x
2
x
n
x
Λ
1
q