Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
Σ = {a
1
, . . . , a
m
}
Σ a
1
< a
2
< ··· < a
m
Σ
∗
Σ
∗
Σ
∗
Σ
∗
IN
0
ut
KodMT
KodMT ⊆ (Σ
bool
)
∗
ut
(Σ
bool
)
∗
(Σ
bool
)
∗
ZZ
A a
A A ∪ {a}
A B
A ∪ B
Q
+
IN
0
1
p/q p, q ∈ IN
|Q
+
| |IN
0
×IN
0
|
n
2
n |Q
+
| = |IN
0
|
Q
+
IN × IN
M
IN×IN
M
IN×IN
1, 2, 3 , . . . (i, j) ∈ IN × IN
i j M
IN×IN
IN × IN
IN ×IN
10
···
(1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6) ···
(2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (2, 6) ···
(3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (3, 6) ···
(4, 1) (4, 2) (4, 3) (4, 4) (4, 5) (4, 6) ···
(5, 1) (5, 2) (5, 3) (5, 4) (5, 5) (5, 6) ···
(6, 1) (6, 2) (6, 3) (6, 4) (6, 5) (6, 6) ···
M
IN×IN
(1, 1)
a
1
= (1, 1), a
2
= (2, 1), a
3
= (1, 2), a
4
= (3, 1),
a
5
= (2, 2), a
6
= (1, 3), a
7
= (4, 1), . . .
···
.
.
.
IN × IN
(a, b) < (c, d) ⇐⇒ a + b < c + d (a + b = c + d b < d).
f
f(a, b) =
a + b − 1
2
+ b,
(a, b) b (a + b −1)
a + b − 2
a+b−2
X
i=1
i =
(a + b − 2) ·(1 + a + b −2)
2
=
a + b − 1
2
.
f IN × IN IN
0
ut
···
IN × IN
IN × IN IN
0
IN × IN IN
0
Q
+
h Q
+
IN × IN
h
p
q
= (p, q)
p q
h IN × IN
Q
+
ut
IN
0
× IN
0
× IN
0
A B
A × B
(Q
+
)
i
i
IR IR
IN
0
Q
+
[0, 1]
[0, 1] IN
[0, 1]
f [0, 1] IN f
[0, 1] i
[0, 1]
a
i
= 0.a
i1
a
i2
a
i3
a
i4
a
i5
. . .
f(a
i
) = i a
ij
∈ {0, 1, 2, . . . , 9} j = 1, 2, . . .
f(x) x ∈ [0, 1]
1 0 a
11
a
12
a
13
a
14
. . .
2 0 a
21
a
22
a
23
a
24
. . .
3
0 a
31
a
32
a
33
a
34
. . .
4 0 a
41
a
42
a
43
a
44
. . .
. . .
i
0 a
i1
a
i2
a
i3
a
i4
. . . a
ii
. . .
[0, 1]
f [0, 1] IN f
[0, 1]
M = [a
ij
]
i=1,...,∞,j=1,...,∞
.
c = 0.c
1
c
2
c
3
c
4
c
5
. . . ,
M
f
c
i ∈ IN i M i
c
i
6= a
ii
c
i
/∈ {0, 9}.
a
11
a
22
a
33
. . . M
i
c
i
∈ {1, 2, 3, 4, 5, 6, 7, 8}− {a
ii
}.
c
a
i
i a
ii
c 0 9
c i
c 6= a
i
.
c f
[0, 1] ut
{0, 1}
|[0, 1]| ≤ |P((Σ
bool
)
∗
)|.
P((Σ
bool
)
∗
)
[0, 1]
|P((Σ
bool
)
∗
)| ≥ |[0, 1]|
[0, 1] P((Σ
bool
)
∗
)
[0, 1]
b = 0.b
1
b
2
b
3
. . .
b
i
∈ Σ
bool
i = 1, 2, 3, . . .
Number(b) =
∞
X
i=1
a
i
2
−i
.
f : [0, 1] → P((Σ
bool
)
∗
)
a = 0.a
1
a
2
a
3
a
4
a
5
a
6
a
7
. . .
11
1.000 0.999 1
0.1429 0.1430 0.143
[0, 1]
f(a) = {a
1
, a
2
a
3
, a
4
a
5
a
6
, . . . , a
(
n
2
)
+1
a
(
n
2
)
+2
. . . a
(
n+1
2
)
, . . .}.
f(a) Σ
bool
n n
b c
f(b) 6= f(c).
f
P((Σ
bool
)
∗
) ut
|KodMT| < |P((Σ
bool
)
∗
)|
Σ
bool
|[0, 1]| = |P((Σ
bool
)
∗
)|
w
1
w
2
w
3
. . . w
i
. . .
M
1
d
11
d
12
d
13
. . . d
1i
. . .
M
2
d
21
d
22
d
23
. . . d
2i
. . .
M
3
d
31
d
32
d
33
. . . d
3i
. . .
M
i
d
i1
d
i2
d
i3
. . . d
ii
. . .
w
1
w
2
w
3
w
4
w
5
Σ
bool
M
1
M
2
M
3
M
4
M
5
A = [d
ij
]
i,j=1,...,∞
d
ij
= 1 ⇔ M
i
j w
j
.
i
12
M
i
i
d
i1
d
i2
d
i3
d
i4
d
i5
. . .
A
L(M
i
) = {w
j
| d
ij
= 1 j ∈ IN}.
L
diag
L(M
i
)
L
diag
= {w ∈ (Σ
bool
)
∗
| w = w
i
i ∈ IN
M
i
w
i
}
= {w ∈ (Σ
bool
)
∗
| w = w
i
i ∈ IN d
ii
= 0}.
L
diag
/∈ L
RE
L
diag
/∈ L
RE
L
diag
∈ L
RE
L
diag
= L(M ) M
M
i M = M
i
L
diag
L(M
i
)
w
i
∈ L
diag
⇔ d
ii
= 0 ⇔ w
i
/∈ L(M
i
).
ut
L
2diag
= {w ∈ (Σ
bool
)
∗
| w = w
2i
i ∈ IN
M
i
w
2i
(d
i,2i
= 0)} .
L
2diag
/∈ L
RE
k ∈ IN
0
L
k,diag
= {w ∈ (Σ
bool
)
∗
| w = w
i+k
i ∈ IN
M
i
w
i+k
(d
i,i+k
= 0)} .
k ∈ IN L
k,diag
/∈ L
RE
A
B
• B
• A B
A
A
A B
L
1
⊆ Σ
∗
1
L
2
⊆ Σ
∗
2
Σ
1
Σ
2
L
1
L
2
L
1
≤
R
L
2
L
2
∈ L
R
⇒ L
1
∈ L
R
.
L
1
≤
R
L
2
L
2
L
1
L
2
L
2
= L(A)
A L
1
L
1
= L(B)
B
L
diag
L
RE
L
R
L
1
≤
R
L
2
P
1
P
2
P
2
P
1
P
1
P
2
MT M
x (Σ
1
, L
1
) y
(Σ
2
, L
2
) x (Σ
1
, L
1
) y
(Σ
2
, L
2
) A
(Σ
2
, L
2
) M A
(Σ
1
, L
1
)
L
1
⊆ Σ
∗
1
L
2
⊆ Σ
∗
2
Σ
1
Σ
2
L
1
L
2
L
1
≤
m
L
2
MT M
x ∈ Σ
∗
1
13
L
L /∈ L
R
14
MT B L(B) = L
1
x ∈ Σ
∗
1
MT M
M(x)
MT A
x∈L
1
⇔M(x)∈L
2
A(M(x))
f
M
: Σ
∗
1
→ Σ
∗
2
( ) :
x ∈ L
1
⇔ f
M
(x) ∈ L
2
.
f
M
L
1
L
2
M L
1
L
2
≤
m
≤
R
L
1
≤
R
L
2
L
1
≤
m
L
2
L
1
⊆ Σ
∗
1
L
2
⊆ Σ
∗
2
Σ
1
Σ
2
L
1
≤
m
L
2
L
1
≤
R
L
2
L
1
≤
m
L
2
L
1
≤
R
L
2
A A
L
2
L
2
∈ L
R
B L
1
A MT L(A) = L
2
L
1
≤
m
L
2
M x ∈ Σ
∗
1
M(x) ∈ Σ
∗
2
x ∈ L
1
⇔ M (x) ∈ L
2
.
A M B
L
1
B x ∈ Σ
∗
1
• B M x
M(x)
• B A M(x)
A M (x) B x
A M(x) B x
L(B) = L
1
A B
L
1
∈ L
R
ut
15
M M(x) x ∈ Σ
∗
1
M
≤
m
(L
1
≤
m
L
2
L
2
≤
m
L
3
) ⇒ L
1
≤
m
L
3
.
B L(B) = L
1
A
A
B A
B B
A A
x L
1
x ∈ L
1
x /∈ L
1
x ∈ Σ
∗
1
MT A
MT B
L(B) = L
1
L(A) = L
2
L /∈ L
R
L
L
R
L
R
Σ L ⊆ Σ
∗
L ≤
R
L
{
L
{
≤
R
L.
L
{
≤
R
L L
(L
{
)
{
= L L
{
≤
R
L (L
{
)
{
≤
R
L
{
L
{
≤
R
L L
{
L
A (L, Σ)
B L
{
B
x ∈ Σ
∗
A A
L
{
≤
R
L
A = (Q, Σ, Γ, δ, q
0
, q
accept
, q
reject
) MT
L
1
B =
(Q, Σ, Γ, δ, q
0
, q
0
accept
, q
0
reject
)
q
0
accept
= q
reject
q
0
reject
= q
accept
;
A A B
L(B) = (L(A))
{
L L
{
ut