Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
x ∈ L
{
x /∈ L
{
x ∈ L
x /∈ L
x ∈ Σ
∗
MT A
MT B
L(B) = L
{
(L
diag
)
{
/∈ L
R
L
diag
/∈ L
RE
L
diag
/∈ L
R
L
diag
≤
R
(L
diag
)
{
.
≤
R
(L
diag
)
{
∈ L
R
L
diag
∈ L
R
.
(L
diag
)
{
/∈ L
R
ut
L
U
L
H
(L
empty
)
{
L
diag
(L
diag
)
{
L
R
L
RE
(L
diag
)
{
L
RE
(L
diag
)
{
∈ L
RE
L
R
( L
RE
(L
diag
)
{
∈ L
RE
L
diag
(L
diag
)
{
= {x ∈ (Σ
bool
)
∗
| x = w
i
i ∈ IN,
M
i
w
i
}.
D (L
diag
)
{
x ∈ (Σ
bool
)
∗
i x i w
i
Σ
bool
Kod(M
i
) i M
i
M
i
w
i
= x
M
i
w
i
D x
M
i
w
i
D x = w
i
M
i
w
i
w
i
/∈ L(M
i
) D
D
x x /∈ L(D)
L(D) = (L
diag
)
{
ut
(L
diag
)
{
∈ L
RE
− L
R
L
R
( L
RE
.
L
RE
L
U
= {Kod(M)#w | w ∈ (Σ
bool
)
∗
M w}.
U MT
L(U) = L
U
.
L
U
∈ L
RE
MMT U L(U) = L
U
U
z ∈ {0 , 1, #}
∗
U z U
U z
z = y#x y , z ∈ (Σ
bool
)
∗
U y
y MT U
z = y#x y MT U
y = Kod(M) M U
M x
U M x
M
q
accept
q
reject
M
16
q
reject
M
U Kod(M)
M q
accept
U z = Kod(M)#x
U z = Kod(M )#x
M x
U Kod(M)#x U
Kod(M)#x L(U) = L
U
ut
L
U
∈ L
RE
MT
L
U
/∈ L
R
M x
M x M x
M
x M
M x
x L(M )
L
U
/∈ L
R
(L
diag
)
{
≤
R
L
U
(L
diag
)
{
/∈ L
R
L
U
/∈ L
R
A L
U
B A
(L
diag
)
{
B x ∈ (Σ
bool
)
∗
C i x = w
i
C
Kod(M
i
) i C
17
18
19
w
i
Kod(M
i
) A B
A
L(B) = (L
diag
)
{
B
C A
(L
diag
)
{
≤
R
L
U
x ∈ (Σ
bool
)
∗
C
x = w
i
A
L(A) = L
U
Kod(M
i
)
w
i
∈ L(M
i
)
w
i
/∈ L(M
i
)
B L(B) = (L
diag
)
{
w
i
∈ (L
diag
)
{
w
i
/∈ (L
diag
)
{
(L
diag
)
{
≤
m
L
U
.
M f
M
(Σ
bool
)
∗
{0, 1, #}
∗
x ∈ (L
diag
)
{
⇔ f
M
(x) ∈ L
U
.
M x
i x = w
i
Kod(M
i
) i MT M
Kod(M
i
)#x x = w
i
(L
diag
)
{
x = w
i
∈ (L
diag
)
{
⇔ M
i
w
i
⇔ w
i
∈ L (M
i
)
⇔ f
M
(x) = Kod(M
i
)#x ∈ L
U
.
{Kod(M)#x#0
i
| x ∈ {0, 1}
∗
, i ∈ IN
0
,
M
i + 1 ,
x
1 i }
(L
diag
)
{
L
U
20
A Kod(M
i
)#w
i
({0, 1, #}
∗
, L
H
)
L
H
= {Kod(M)#x | x ∈ {0, 1}
∗
M x}.
L
H
∈ L
RE
L
H
/∈ L
R
L
U
≤
R
L
H
.
L
H
∈ L
R
A
L
H
B
L
U
A
w B C
w y#x y = Kod(M ) M
x ∈ (Σ
bool
)
∗
y B w
y = Kod(M)#x B y A
A M x B
x /∈ L(M) w = Kod(M )#x
Kod(M)
y =
xx
y
A
C
U
L(A) = L
H
Kod(M)#x
M
x
M
x
M x
B L
U
y#x ∈ L
U
y#x /∈ L
U
M
x
y#x /∈ L
U
y MT
A M x B
M x U
M x U
U M x
B y#x = Kod(M)#x U M
x B
L(B) = L
U
B
L
U
≤
R
L
H
,
M
L
U
L
H
w M
w
w = Kod(M)#x
M x ∈ (Σ
bool
)
∗
• w M Kod(M
1
)
M
1
δ(q
0
, ¢) =
(q
0
, ¢, N)
M
M(w) = Kod(M
1
)#x.
•
w = Kod(M)#x M M
M
2
L(M
2
) = L(M) M
2
M
q
reject
M
p δ(p, a) = (p, a, N)
a ∈ Σ M
2
y y /∈ L(M ) = L(M
2
)
M
M(w) = Kod(M
2
)#x.
w ∈ {0, 1, #}
∗
w ∈ L
U
⇔ M (w) ∈ L
H
.
w ∈ L
U
w = Kod(M)#x M
x ∈ {0, 1}
∗
x ∈ L(M) L(M
2
) = L(M) M
x M(w) = Kod(M
2
)#x
L
H
w /∈ L
U
w Kod(M)#x M
M(w) = Kod(M
1
)#x M
1
M
1
x M(w)
L
H
w Kod(M)#x M Kod(M)#x /∈ L
U
x /∈ L(M) M (w) = Kod(M
2
)#x M
2
(Σ
bool
)
∗
−L(M) x /∈ L(M) M
x Kod(M)#x L
H
ut
21
M
1
• L
U
≤
R
(L
diag
)
{
• L
H
≤
R
(L
diag
)
{
• L
diag
≤
R
L
U
• (L
diag
)
{
≤
R
L
H
• L
H
≤
R
L
U
L
empty
= {Kod(M) | L(M) = ∅}.
(L
empty
)
{
= {x ∈ (Σ
bool
)
∗
| x 6= Kod(M) MT M
x = Kod(M ) L(M) 6= ∅}.
(L
empty
)
{
∈ L
RE
(L
empty
)
{
∈
L
RE
|IN
0
| = |Q
+
|
HMT M
1
MT M
2
L(M
1
) = L(M
2
)
HMT M
1
L(M
1
) = (L
empty
)
{
x
M
1
MT M
x = Kod(M) x M
1
x
x = Kod(M) MT M M
y ∈ (Σ
bool
)
∗
M
y
M y L(M) 6= ∅) M
1
x =
Kod(M)
M y M
1
x
M y M x
x = Kod(M )
M
1
x = Kod(M) MT M L(M ) 6= ∅
y ∈ L(M) M
1
x = Kod(M)
x ∈ L
empty
M
1
x = Kod(M)
L(M
1
) = (L
empty
)
{
.
(L
empty
)
{
∈ L
RE
A
(L
empty
)
{
w A
0
w MT A w
0
w = Kod(M) MT M A
A (i, j) ∈ IN × IN
(i, j) A i w
i
M
j M w
i
(k, l) M w
k
l A
w = Kod(M) A
w
y ∈ L(M)
y = w
k
k
M y l
(i, j)
0
A
A w ut
(L
empty
)
{
/∈ L
R
(L
empty
)
{
/∈ L
R
L
U
≤
m
(L
empty
)
{
.
A L
U
(L
empty
)
{
x ∈ {0, 1, #} A
• x Kod(M)#w M
w ∈ (Σ
bool
)
∗
A A(x) = Kod(B
x
) B
x
Σ
bool
L(B
x
) = ∅
• x = Kod(M )#w M w ∈ (Σ
bool
)
∗
A
Kod(B
x
) B
x
y B
x
B
x
x = Kod(M)#w
{ x
B
x
}
22
A B
x
δ
B
x
δ(q
0
, ¢) = (q
reject
, ¢, N)
23
B
x
∅ (Σ
bool
)
∗
B
x
M w
M w B
x
y
M w B
x
y
M w B
x
y B
x
y
x ∈ {0, 1, #}
∗
x ∈ L
U
⇔ A(x) = Kod(B
x
) ∈ (L
empty
)
{
.
x ∈ L
U
x = Kod(M )#w M w ∈ L(M )
L(B
x
) = (Σ
bool
)
∗
6= ∅ Kod(B
x
) ∈ (L
empty
)
{
x /∈ L
U
x Kod(M
0
)#z
M
0
z ∈ {0 , 1}
∗
x = Kod(M )#w M
w /∈ L (M ) L(B
x
) = ∅ Kod(B
x
) /∈ (L
empty
)
{
ut
x
w
Kod(M)
Kod(B
x
)
MT E
A
L(E) =
(L
empty
)
{
L(B
x
) 6= ∅
L(B
x
) = ∅
M
w
M
w
L
empty
/∈ L
R
L
empty
∈ L
R
(L
empty
)
{
∈ L
R
ut
∗
L
RE
• L
empty
• (L
H
)
{
• (L
U
)
{
L
EQ
= {Kod(M)#Kod(M) | L(M ) = L(M)}
L
EQ
/∈ L
R
L
empty
L
EQ
L
empty
≤
m
L
EQ
.
A Kod(M)
Kod(M)#Kod(C)
C
L(C) = ∅
Kod(M)#Kod(C) ∈ L
EQ
⇔ L(M) = L(C) = ∅ ⇔ Kod(M) ∈ L
empty
,
ut
{Kod(M)#Kod(M ) | L(M) ⊆ L(M)}
L
R
A x
A x
L(M) 6= ∅
M
L ⊆ {Kod(M) | M MT}
MT M
1
Kod(M
1
) ∈ L L 6= ∅
MT M
2
Kod(M
2
) /∈ L L
A B L(A) = L(B)
Kod(A) ∈ L ⇐⇒ Kod(B) ∈ L.
24