Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
L
H,λ
= {Kod(M) | M λ}
L
H,λ
/∈ L
R
.
L
H
≤
m
L
H,λ
.
A L
H
L
H,λ
x Kod(M )#w A MT H
x
x = Kod(M)#w M w
A Kod(H
x
) H
x
MT H
x
x =
Kod(M)#w
H
x
M w M
H
x
M w H
x
x ∈ {0, 1, #}
∗
x ∈ L
H
⇔ x = Kod(M)#w M w
⇔ H
x
⇔ H
x
λ
⇔ Kod(H
x
) ∈ L
H,λ
ut
∗
L
L
H,λ
≤
m
L, L
H,λ
≤
m
L
{
.
M
∅
MT L(M
∅
) = ∅
Kod(M
∅
) L
25
H
x
M
w H
x
M
w
Kod(M
∅
) ∈ L
L
H,λ
≤
m
L
{
.
M
Kod(M) /∈ L
S L
H,λ
L
{
x ∈ (Σ
bool
)
∗
S
• S(x) = Kod(M
0
) L(M
0
) = L(M
∅
) = ∅
Kod(M
0
) /∈ L
{
x /∈ L
H,λ
• S(x) = Kod(M
0
) L(M
0
) = L(M)
Kod(M
0
) ∈ L
{
x ∈ L
H,λ
L S
x ∈ (Σ
bool
)
∗
S x = Kod(M) MT M x
S
S(x) = Kod(M
∅
)
x = Kod(M) MT M S Kod(M
0
)
M
0
M
0
Σ
M
M Kod(M) /∈ L Kod(M) ∈ L
{
y ∈ (Σ
M
)
∗
M
0
x =
Kod(M) y y
M λ
M λ Kod(M) /∈ L
H,λ
M
0
y y /∈ L(M
0
)
{ M λ
M
0
y M
0
L(M
0
) = ∅ =
L(M
∅
)
Kod(M
0
) ∈ L Kod(M
0
) /∈ L
{
).}
M λ Kod(M) ∈ L
H,λ
M
0
Kod(M) M M
0
M y ∈ (Σ
M
)
∗
M
0
y M y
{ L(M
0
) = L(M) Kod(M
0
) /∈ L Kod(M
0
) ∈
L
{
.}
x ∈ L
H,λ
⇔ S(x) ∈ L
{
x ∈ (Σ
bool
)
∗
L
H,λ
≤
m
L
{
Kod(M
∅
) /∈ L
˜
M
Kod(
˜
M) ∈ L L
H,λ
≤
m
L
L
H,λ
≤
m
L
{
˜
M
M ut
L
H,λ
≤
m
L
Kod(M
∅
) /∈ L
L
Kod
L
= {Kod(M) | M MT L(M) = L}
L
L Kod
L
6= ∅
Kod
L
Kod
L
Kod
L
Kod
L
/∈ L
R
Σ L ⊆ Σ
∗
L, L
{
∈ L
RE
⇔ L ∈ L
R
.
(x, y) x y Σ (x, y)
(x, y)
s
1
= (1, #0) s
2
= (0, 01) s
3
= (#0, 0) s
4
= (01#, #)
{0, 1, #}
s
1
s
2
s
3
s
4
s
2
, s
1
, s
3
, s
2
, s
4
01#0001#
26
s
1
= (00 , 001) s
2
= (0, 001) s
3
= (1, 11)
Σ
Σ (A, B)
A = w
1
. . . w
k
, B = x
1
. . . x
k
k w
i
, x
i
∈ Σ
∗
i = 1, . . . , k
i ∈ { 1, . . . , k} (w
i
, x
i
)
(A, B)
k
i
1
, i
2
, . . . , i
m
w
i
1
w
i
2
. . . w
i
m
= x
i
1
x
i
2
. . . x
i
m
.
i
1
i
2
. . . i
k
(A, B)
(i
1
i
2
. . . i
k
)
j
(A, B) j ut
(L
PCP
, Σ
bool
)
L
PCP
⊆ (Σ
bool
)
∗
L
PCP
∈ L
RE
((10, 011, 101) (101, 11, 011))
((1, 1110111, 1 01)
(111, 1110, 0 1))
27
28
Σ
Σ
(C, D)
C = u
1
. . . u
k
, D = v
1
. . . v
k
k u
i
, v
i
∈ Σ
∗
i = 1, . . . , k
(C, D)
m m
j
1
, j
2
, . . . , j
m
u
1
u
j
1
u
j
2
. . . u
j
m
= v
1
v
j
1
v
j
2
. . . v
j
m
.
Σ
(A, B)
A = 0, 11, 1 B = 001 , 1, 11,
s
1
= (0, 001) s
2
= (11, 1) s
3
= (1, 11).
s
2
s
3
(A, B) (A, B)
(A, B)
((0, 11, 1) (001, 1, 11))
(A, B) (C, D)
(A, B) ⇐⇒ (C, D)
A = w
1
. . . w
k
B = x
1
. . . x
k
,
Σ k w
i
, x
i
∈ Σ
∗
i = 1, . . . , k $, ¢ /∈ Σ
(C, D) Σ
1
= Σ ∪ {¢, $}
29
h
L
h
R
Σ
∗
Σ
∗
1
a ∈ Σ
h
L
(a) = ¢a h
R
(a) = a¢.
h
L
¢ h
R
¢ 0110
h
L
(0110) = ¢0¢1¢1¢0 h
R
(0110) = 0¢1¢1¢0¢.
C = y
1
y
2
. . . y
k+2
D = z
1
z
2
. . . z
k+2
,
y
1
= ¢h
R
(w
1
) z
1
= h
L
(x
1
)
y
2
= h
R
(w
1
) z
2
= h
L
(x
1
)
y
3
= h
R
(w
2
) z
3
= h
L
(x
2
)
y
i+1
= h
R
(w
i
) z
i+1
= h
L
(x
i
)
y
k+1
= h
R
(w
k
) z
k+1
= h
L
(x
k
)
y
k+2
= $ z
k+2
= ¢$.
((0, 11, 1) (001, 1, 11))
((¢0¢, 0¢, 1¢1¢, 1¢, $), (¢0¢0¢1, ¢0¢0¢1, ¢1, ¢1¢1, ¢$)).
MT
(C, D) (A, B)
(A, B) (C, D)
• (A, B)
(C, D) i
1
, i
2
, . . . , i
m
(A, B)
u = w
1
w
i
1
w
i
2
. . . w
i
m
= x
1
x
i
1
x
i
2
. . . x
i
m
.
2 i
1
+ 1 i
2
+ 1 . . . i
m
+ 1,
(C, D) h
R
w
1
w
i
1
w
i
2
. . . w
i
m
h
L
x
1
x
i
1
x
i
2
. . . x
i
m
¢h
R
(u) = ¢y
2
y
i
1
+1
. . . y
i
m
+1
= z
2
z
i
1
+1
. . . z
i
m
+1
¢ = h
L
(u)¢.
h
R
(u) = y
2
y
i
1
+1
. . . y
i
m
+1
h
L
(u) = z
2
z
i
1
+1
. . . z
i
m
+1
¢
(C, D) y
1
= ¢y
2
z
1
= z
2
2 1
1 i
1
+ 1 i
2
+ 1 . . . i
m
+ 1,
y
1
y
i
1
+1
y
i
2
+1
. . . y
i
m
+1
= z
1
z
i
1
+1
z
i
2
+1
. . . z
i
m
+1
¢.
¢
(C, D) (k + 2) (¢, ¢$)
y
1
y
i
1
+1
y
i
2
+1
. . . y
i
m
+1
y
k+2
= z
1
z
i
1
+1
z
i
2
+1
. . . z
i
m
+1
z
k+2
,
1 i
1
+ 1 i
2
+ 1 . . . i
m
+ 1 k + 2
(C, D)
• (C, D)
(A, B)
z
i
¢ y
1
¢ y
i
(C, D)
(k + 2 ) (C, D)
k + 2
1 j
1
j
2
. . . j
m
k + 2
(C, D)
1, j
1
− 1, j
2
− 1, . . . , j
m
− 1
(C, D)
¢ $ y
1
y
j
1
y
j
2
. . . y
j
m
y
k+2
w
1
w
j
1
−1
w
j
2
−1
. . . w
j
m
−1
¢ $ z
1
z
j
1
z
j
2
. . . z
j
m
z
k+2
x
1
x
j
1
−1
x
j
2
−1
. . . x
j
m
−1
x
k+2
1, j
1
, . . . j
m
, k + 2 (C, D)
y
1
, y
j
1
y
j
2
. . . y
j
m
y
k+2
= z
1
z
j
1
z
j
2
. . . z
j
m
z
k+2
.
w
1
w
j
1
−1
w
j
2
−1
. . . w
j
m
−1
= x
1
x
j
1
−1
x
j
2
−1
. . . x
j
m
−1
.
1, j
1
− 1, j
2
− 1, . . . , j
m
− 1
(A, B)
30
h
L
(u) h
R
(u)
ut
∗
L
U
x ∈ {0, 1, #}
∗
(A, B)
x ∈ L
U
⇐⇒ (A, B) .
x Kod(M )#w MT M w ∈ {0, 1}
∗
x /∈ L
U
A = 0 B = 1
(0, 1)
x = Kod(M)#w M =
(Q, Σ, Γ, δ, q
0
, q
accept
, q
reject
) w ∈ Σ
∗
M
(C, D)
• B M w
• A
δ
q
accept
# Γ
(#, #q
0
¢w#).
M w
M w
q
0
¢w#
(X, X) X ∈ Γ ;
(#, #).
|Γ | + 1
M
q ∈ Q − {q
accept
} p ∈ Q X, Y, Z ∈ Γ
(qX, Y p), δ(q, X) = (p, Y, R);
(ZqX, pZY ), δ(q, X) = (p, Y, L);
(q#, Y p#),
δ(q,
t
) = (p, Y, R);
(Zq#, pZY #), δ(q ,
t
) = (p, Y, L).
M w q
accept
q
accept
Γ ∪{¢} X, Y ∈ Γ ∪{¢}
(Xq
accept
Y, q
accept
);
(Xq
accept
, q
accept
);
(q
accept
Y, q
accept
).
q
accept
q
accept
#
(q
accept
##, #)
(A, B)
M = ({q
0
, q
1
, q
accept
, q
reject
}, {0, 1}, {¢, 0, 1,
t
}, δ
M
, q
accept
, q
reject
),
w = 01
(#, #q
0
¢01#).
(0, 0), (1, 1), (¢, ¢), ($, $), (#, #).
(q
0
1, 1q
0
), (q
0
0, 0q
1
), (q
0
¢, ¢q
1
),
(1q
0
#, q
accept
1#), (0q
0
#, q
accept
0#)
(q
1
1, 1q
1
), (q
1
0, 0q
0
), (1q
1
#, q
reject
1#), (0q
1
#, q
reject
0#).
(0q
accept
0, q
accept
), (1q
accept
1, q
accept
), (1q
accept
0, q
accept
),
(0q
accept
1, q
accept
), (0q
accept
, q
accept
), (1q
accept
, q
accept
),
(q
accept
0, q
accept
), (q
accept
1, q
accept
),
(¢q
accept
, q
accept
), (q
accept
¢, q
accept
),
(¢q
accept
a, q
accept
), (aq
accept
¢, q
accept
)
a ∈ {0, 1}
(q
accept
##, #)
M 01
(A, B)
M
M w ⇐⇒ (A, B)
w ∈ L(M) M w
(A, B) (#, #q
0
¢w#)
#
q
accept
(A, B)
w /∈ L (M ) (A, B)
(#, #q
0
¢w#)
M q
accept
(A, B) ut
(A, B)
(A, B)
M w
w ∈ L(M)
• M w
#
•
ut
∗
{0}
31