Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
x
xx
x
y
y z
z
q
0
q
0
p p
pppp
r
r
L ⊆ Σ
∗
A = (Q, Σ, δ
A
, q
0
, F ) L(A) = L
n
0
= |Q|.
w Σ |w| ≥ n
0
w = w
1
w
2
. . . w
n
0
u,
w
i
∈ Σ i = 1, . . . , n
0
u ∈ Σ
∗
A w
1
w
2
. . . w
n
0
(q
0
, w
1
w
2
w
3
. . . w
n
0
)
|−−
A
(q
1
, w
2
w
3
. . . w
n
0
)
|−−
A
(q
2
, w
3
. . . w
n
0
)
|−−
A
···
|−−
A
(q
n
0
−1
, w
n
0
)
|−−
A
(q
n
0
, λ).
n
0
+ 1 q
0
, q
1
, q
2
, . . . , q
n
0
n
0
+ 1
|Q| = n
0
i, j ∈ {0 , 1, . . . , n
0
} i < j q
i
= q
j
(q
0
, w
1
. . . w
n
0
)
∗
|−−
A
(q
i
, w
i+1
. . . w
n
0
)
∗
|−−
A
(q
i
, w
j+1
. . . w
n
0
)
∗
|−−
A
(q
n
0
, λ).
y = w
1
. . . w
i
, x = w
i+1
. . . w
j
z = w
j+1
. . . w
n
0
u.
w = yxz
w y x z
yx = w
1
. . . w
i
w
i+1
. . . w
j
|yx| = j ≤ n
0
i < j |x| = j − i x 6= λ |x| ≥ 1
y w
1
. . . w
i
x w
i+1
. . . w
j
A yx
(q
0
, yx)
∗
|−−
A
(q
i
, x)
∗
|−−
A
(q
i
, λ).
k ∈
IN
0
(q
i
, x
k
)
∗
|−−
A
(q
i
, λ).
k ∈ IN
0
(q
0
, yx
k
z)
∗
|−−
A
(q
i
, x
k
z)
∗
|−−
A
(q
i
, z)
∗
|−−
A
(
ˆ
δ
A
(q
i
, z), λ)
A yx
k
z
k ∈ IN
0
ˆ
δ
A
(q
i
, z)
ˆ
δ
A
(q
i
, z) ∈ F
A {yx
k
z | k ∈ IN
0
}
ˆ
δ
A
(q
i
, z) /∈ F
A
ut
L = {0
n
1
n
| n ∈ IN
0
}
L
n
0
w n
0
L /∈ L(KA) w |w| ≥ n
0
3
w = 0
n
0
1
n
0
.
|w| = 2n
0
≥ n
0
w w = yxz
|yx| ≤ n
0
y = 0
l
x = 0
m
l, m ∈ IN
0
m 6= 0
w = 0
n
0
1
n
0
= yxz ∈ L
yxz ∈ {yx
k
z | k ∈ IN
0
},
{yx
k
z | k ∈ IN
0
} = {0
n
0
−m+km
1
n
0
| k ∈ IN
0
} ⊆ L.
yx
0
z = yz = 0
n
0
−m
1
n
0
/∈ L.
0
n
0
1
n
0
{yx
k
z | k ∈ IN
0
}
L L
w
L /∈ L(KA) L = {0
n
1
n
|
n ∈ IN
0
}
w = 0
n
0
/∈ L :
w
w = yxz y = 0, x = 0 z = 0
n
0
−2
.
w
{yx
k
z | k ∈ IN
0
} = {0
n
0
−1+k
| k ∈ IN
0
}
L w = yxz
L L /∈ L(KA)
w = 0
dn
0
/2e
1
dn
0
/2e
.
L = {0
n
1
n
| n ∈ IN
0
}
yxz w
y = 0
i
x = 0
m
z = 0
dn
0
/2e−m−i
1
dn
0
/2e
i ∈ IN
0
m ∈ IN x
0
w = 0
n
0
1
n
0
y = 0
dn
0
/2e−m
x = 0
m
1
j
z = 1
dn
0
/2e−j
m j x
0 1
x = yxz ∈ L yx
2
z /∈ L
yx
2
z a
∗
b
∗
y = 0
dn
0
/2e
1
i
x = 1
m
z = 1
dn
0
/2e−i−m
i ∈ IN
0
m ∈ IN
0
dn
0
/2e
1
dn
0
/2e
L /∈
L(KA)
0
n
0
1
n
0
• {ww | w ∈ {0, 1}
∗
}
• {a
n
b
n
c
n
| n ∈ IN
0
}
• {w ∈ {0, 1}
∗
| |w|
0
= |w|
1
}
• {a
n
2
| n ∈ IN
0
}
• {a
2
n
| n ∈ IN
0
}
18
0
n
0
1
n
0
x 0
w = 0
dn
0
/2e
1
dn
0
/2e
x w
• {w ∈ {0, 1}
∗
| |w|
0
= 2|w|
1
}
• {x1y | x, y ∈ {0, 1}
∗
, |x| = |y|}
Σ
bool
yxz
L ⊆ Σ
∗
n
0
∈ IN
0
w ∈ Σ
∗
|w| ≥ n
0
w = yxz
• |xz| ≤ n
0
• |x| ≥ 1
• {yx
k
z | k ∈ IN
0
} ⊆ L {yx
k
z | k ∈ IN
0
} ∩ L = ∅
∗
L /∈ L(KA )
∗
L ⊆ (Σ
bool
)
∗
x ∈ Σ
∗
L
x
= {y ∈ Σ
∗
| xy ∈ L}.
const x, y ∈ Σ
∗
K (y) ≤ dlog
2
(n + 1)e + const.
y n L
x
L
M L(M ) = L
z ∈ Σ
∗
M
xz xz ∈ L = L(M) n
xz x z n
L
x
z
n y L
x
n M x
x K (x)
K (y)
19
z ∈ L
x
y x
M
ˆ
δ(q
0
, x)
z
ˆ
δ(q
0
, x)
M xz z
q
0
y n L
x
x ∈ Σ
∗
A
x,y
y
A
x,y
z := λ i := 0
i < n
M
ˆ
δ(q
0
, x)
z
ˆ
δ(
ˆ
δ(q
0
, x), z) ∈ F
i := i + 1
y := z
z := z
(y)
x, y ∈ Σ
∗
A
x,y
n
ˆ
δ(q
0
, x)
M
ˆ
δ(q
0
, x)
|Q|
const
M
M
A
x,y
n M
ˆ
δ(q
0
, x)
d x
y n
dlog
2
(n + 1)e
K (y) ≤ dlog
2
(n + 1)e + const
M
+ d.
ut
L = {0
n
1
n
| n ∈ IN
0
} /∈ L(KA).
L m ∈ IN
0
1
m
L
0
m
= {y | 0
m
y ∈ L} = {0
j
1
m+j
| j ∈ IN
0
}.
c m
1
m
K (1
m
) ≤ K (1) + c.
K (1)
K (1
m
) ≤ d
d = K (1) + c m ∈ IN
• d
• {1
m
| m ∈ IN
0
}
m
K (m) ≥ dlog
2
(m + 1)e − 1.
b ∈ IN
0
m ∈ IN
0
|K (1
m
) −K (m)| ≤ b
m ∈ IN
0
b m ∈
IN
0
|K (1
m
) − K (m)| ≤ b.
• {0
n
2
| n ∈ IN
0
}
• {0
2
2n
| n ∈ IN
0
}
• {w ∈ {0, 1}
∗
| |w|
0
= 2 · |w|
1
}
• {w ∈ {0, 1}
∗
| w = xx x ∈ {0, 1}
∗
}
20
2
d
21
(Σ, L)
A L
x ∈ L
A x y ∈ Σ
∗
− L
A y
,
i j
HKA
M = (Q, Σ, δ, q
0
, F )
• Q
• Σ
• q
0
∈ Q
• F ⊆ Q
22
23
24
a
a
a
• δ Q × Σ P(Q)
,
{ Q Σ q
0
F
δ q
b HKA 0
δ(q, b)
}
M
Q × Σ
∗
(q
0
, x)
x
M
|−−
M
⊆ (Q × Σ
∗
) × (Q × Σ
∗
),
(q, w)
|−−
M
(p, x) ⇔ w = ax
a ∈ Σ p ∈ δ(q, a).
M D
1
, D
2
, . . . , D
k
i = 1, . . . , k − 1 D
i
|−−
M
D
i+1
x C
0
, C
1
, . . . , C
m
M
• C
0
= (q
0
, x) C
0
M x
• C
m
∈ Q × {λ}
C
m
= (q, ax) a ∈ Σ q ∈ Q δ(q, a) = ∅
{ M x
25
δ (Q×Σ)×Q
26
(q, a).}
C
0
, C
1
, . . . , C
m
M x C
m
= (p, λ)
p ∈ F
{M x C x
}
M x M
x
∗
|−−
M
|−−
M
M
L(M) = {w ∈ Σ
∗
| (q
0
, w)
∗
|−−
M
(p, λ)
p ∈ F }.
δ
ˆ
δ
Q ×Σ
∗
P(Q)
q ∈ Q, a ∈ Σ w ∈ Σ
∗
•
ˆ
δ(q, λ) = {q}
•
ˆ
δ(q, wa ) = {p | r ∈
ˆ
δ(q, w) p ∈ δ(r, a)}
=
S
r∈
ˆ
δ(q,w)
δ(r, a)
x L(M)
M x
M
δ(q, a) = ∅ q a
ˆ
δ
ˆ
δ(q
0
, w)
Q w
q
0
ˆ
δ(q
0
, w) = {p ∈ Q | (q
0
, w)
∗
|−−
M
(p, λ)}.
L(M) = {w ∈ Σ
∗
|
ˆ
δ(q
0
, w) ∩ F 6= ∅}
M
M =
(Q, Σ, δ, q
0
, F )
Q = {q
0
, q
1
, q
2
}
Σ = {0, 1}
F = {q
2
}
27
28
q
0
q
1
q
2
0, 10, 1
1
1
δ(q
0
, 0) = {q
0
} δ(q
0
, 1) = {q
0
, q
1
}
δ(q
1
, 0) = ∅ δ(q
1
, 1) = {q
2
}
δ(q
2
, 0) = {q
2
} δ(q
2
, 1) = {q
2
}
HKA M
L(M) 10110
(q
0
, 10110)
|−−
M
(q
0
, 0110)
|−−
M
(q
0
, 110)
|−−
M
(q
1
, 10)
|−−
M
(q
2
, 0)
|−−
M
(q
2
, λ)
M 10110
HKA M x
M x
B
M
(x) M x
M B
M
(x)
M x (q, α)
(q, α) (p, β) (q, α)
|−−
M
(p, β)
B
M
(x) (r, λ) (s, aβ)
a ∈ Σ δ(s, a) = ∅
B
M
(x) M
x B
M
(x)
M x
HKA 2
|x|
x ∈ (Σ
bool
)
∗
M B
M
(x)
M x = 10110 B
M
(10110 )
(q
1
, 0110) (q
1
, 0)
M δ(q
1
, 0) = ∅
(q
0
, λ) (q
2
, λ)
10110 q
2
∈
F
10110 ∈
L(M)
q
2
M
q
2
q
0
11
29
(q
2
, λ)