ВУЗ:
Составители:
Рубрика:
Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
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
128
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
ЗАДАЧИ И УПРАЖНЕНИЯ
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 15 ; 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 2 x 3 x n x1 .
Указание: В начальной конфигурации
↓
Λ x1 x2 … … xn Λ
q1
