Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
L
diag
L
diag
K (x) x ∈ (Σ
bool
)
∗
K (x)
x ∈ (Σ
bool
)
∗
A
K (x) x ∈ (Σ
bool
)
∗
x
n
Σ
bool
K (x
n
) ≥ n.
A n B
n
• A
• x
n
λ
B
n
B
n
x := λ
K (x) A
K (x) < n
x := x
K (x) A
(x)
n B
n
x
n
B
n
n c
32
33
K (Σ
bool
)
∗
(Σ
bool
)
∗
(Σ
bool
)
∗
IN
0
K (x)
x
K
B
n
n n ∈ IN
0
B
n
dlog
2
(n + 1)e + c
c n B
n
x
n
n
K (x
n
) ≤ dlog
2
(n + 1e + c.
x
n
n ∈ IN
K (x
n
) ≥ n.
dlog
2
(n + 1)e + c ≥ K (x
n
) ≥ n
A K (x) x ut
n
x
n
K (x
n
) ≥ n
L
U
L
H
L
empty
K
L
H
/∈ L
R
L
H
∈ L
R
K (x) x ∈ (Σ
bool
)
∗
L
H
∈ L
R
H
L
H
A K (x)
x ∈ (Σ
bool
)
∗
A w
1
, w
2
, w
3
, . . .
i A w
i
w
i
A
w
i+1
w
i
= Kod(M) M A
H M λ
M λ A M
λ
M u = M (λ) A
u = x u = x A
K (x) = |w
i
|.
u 6= x A w
i+1
34
A
n
|w
i
| A x w
i
w
i
= Kod(M )
M M x A
K(x) x ∈ (Σ
bool
)
∗
ut
• L
U
∈ L
R
K (x)
x ∈ (Σ
bool
)
∗
• L
empty
∈ L
R
K (x)
x ∈ (Σ
bool
)
∗
•
•
•
A
B
B A A
|A| = |A × A| |IN
0
| = |Q
+
|
IN
0
C |C| ≤ |IN
0
|
B |B| > |IN
0
|
{0, 1}
|A| < |B| A B
B − A
L
M
q
accept
q
reject
L
L
diag
L
diag
M w w ∈ L(M)
35
36
M w
M
M
w
L
i
i ∈ IN L L
i
L
L
1
, L
2
. . . L
i−1
37
38
39
x ∈ {0, 1}
∗
x
S
x = Kod(M) MT M
S MT M
0
M
0
M λ
M λ
M
0
M
S(x) = Kod(M
0
)
L(M
0
) = ∅ = L(M
∅
)
M λ
L(M
0
) = L(M)
Kod(M) ∈ L
{
M
MT
L
{
S(x) ∈ L
{
S(x) /∈ L
{
M
M
x
MT
S(x) = Kod(M
∅
)
Kod(M
∅
) /∈ L
{
MT L
H,λ
x
1
y
1
x
2
y
2
x
n
y
n
. . .
1
0
0
#0
#0
01
#
01#
s
1
s
2
s
3
s
4
1
0
00
#0
#0
0101
#
01#
s
1
s
2
s
2
s
3
s
4
11
11
0000
0000
##
##
s
1
s
2
s
2
s
3
s
4
0 → 0, R
0 → 0, R
1 → 1, R
0 → 1, R
¢ → ¢, R
t
→
t
, L
t
→
t
, L
q
0
q
1
q
accept
q
reject
q
0
q
0
q
0
q
0
q
0
q
0
q
1
q
1
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
¢
¢
¢
¢
¢
¢
¢
¢
¢
#
#
#
#
#
##
#
#
##
q
accept
···
0
0
1
1
¢
¢
¢
¢
#
#
#
#
#
#
#
#
#
#
q
accept
q
accept
q
accept
q
accept
q
accept
q
accept
x ∈ {0, 1}
∗
x
w
i
w
i
= Kod(M)
M
λ Kod(M) = w
i
MT H
w
1
, w
2
, w
3
, . . .
L(H) = L
H
M λ
M(λ)
M(λ) = x
|Kod(M )|
i = i + 1
M
λ
A
A(x) = K(x)
x ∈ {0, 1}
∗
•
•
•
NP
1
2