Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
B q A
B 0 B ¢w$
A i ∈ {1, . . . , k} (2i)
B ¢x
i
i A
↑ (2i + 1) i
A
A
B
B
B k + 1 k + 1
A
↑
B
A B
↑
A
A
A B
• A ∈ A B ∈ B A
• B ∈ B A ∈ A
B
Σ
∗
Γ
∗
ut
16
A B
17
B Q ×
(Σ ∪ {¢, $}) × Γ
k
18
A B
M
C
MT
C
MT
M
w M
M w
I J I · J
+1 I := I + 1 −1 I := I − 1
0 I = 0
I ≥ J 1 2
+1 I := I + 1 −1 I := I − 1 0
19
I J I − J I + J
+1 −1 0
• I := I + 1
• I := I − 1
• I = 0
MMT x#y x
I
x
y I
x
+1 −1 y = 0
MMT
¢x#y##z#u## . . .
I
x
y MMT
##z#u ## . . .
y
•
•
20
1 I
x
δ
Q × Γ → Q ×Γ × {L, R, N},
Q × Γ → P(Q ×Γ × {L, R, N}).
δ
(Q × Γ ) × (Q ×Γ ×{L, R, N}).
M w
M
w
M
HMT
M = (Q, Σ, Γ, δ, q
0
, q
accept
, q
reject
)
• Q, Σ, Γ, q
0
, q
accept
, q
reject
MT
21
22
• δ : (Q−{q
accept
, q
reject
})×Γ → P(Q×Γ ×{L, R, N})
M
δ(p, ¢) ⊆ {(q, ¢, X) | q ∈ Q, X ∈ {R, N}}
p ∈ Q − {q
accept
, q
reject
}
{
¢ }
M
conf(M ) = ({¢} · Γ
∗
·Q · Γ
∗
) ∪ (Q · {¢} · Γ
∗
).
{
MT }
w ∈ Σ
∗
q
0
¢w
M w
q
accept
q
reject
M
|−−
M
( (
|−−
M
⊆ conf(M) ×conf(M ))
p, q ∈ Q x
1
, x
2
, . . . , x
n
, y ∈ Γ
• x
1
x
2
. . . x
i−1
qx
i
x
i+1
. . . x
n
|−−
M
x
1
x
2
. . . x
i−1
pyx
i+1
. . . x
n
(p, y, N) ∈ δ(q, x
i
)
• x
1
x
2
. . . x
i−2
, x
i−1
qx
i
x
i+1
. . . x
n
|−−
M
x
1
x
2
. . . x
i−2
px
i−1
yx
i+1
. . . x
n
(p, y, L) ∈ δ(q, x
i
)
• x
1
x
2
. . . x
i−1
qx
i
x
i+1
. . . x
n
|−−
M
x
1
x
2
. . . x
i−1
ypx
i+1
. . . x
n
(p, y, R) ∈ δ(q, x
i
) i < n
• x
1
x
2
. . . x
n−1
qx
n
|−−
M
x
1
x
2
. . . x
n−1
yp
t
(p, y, R) ∈ δ(q, x
n
)
∗
|−−
M
|−−
M
M C
0
, C
1
, . . .
i = 0, 1, 2, . . .
C
i
|−−
M
C
i+1
{
C
0
|−−
M
C
1
|−−
M
C
2
|−−
M
. . . C
0
, C
1
, C
2
. . .}
M x
q
0
¢x
w
1
qw
2
q ∈ {q
accept
, q
reject
} M x
M x
M w
M w M w
M w
L(M) M
L(M) = {w ∈ Σ
∗
| q
0
¢w
∗
|−−
M
yq
accept
z
y, z ∈ Γ
∗
}
= {w ∈ Σ
∗
|
}.
k
M
HMT M
0
L(M) = L(M
0
)
L
unequal
= {x#y | x, y ∈ (Σ
bool
)
∗
, x 6= λ, x 6= y}.
MT x y
x y x = x
1
x
2
. . . x
n
y = y
1
y
2
. . . y
m
x
j
y
l
∈ Σ
j = 1, . . . n l = 1, 2, . . . m x y HMT i
x y x
i
y
i
1 MT A L
unequal
A
w A
A # w
1
q
0
, q
1
, q
reject
w # A w
w = x#y x, y ∈ (Σ
bool
)
∗
A
2 q
2
A ¢
A q
2
A
t
a ∈ Γ − {0, 1, #} A
x
x y q
guess
b ∈ { 0, 1} A
x y 4
A
A #
4 |x| 6= |y|
¢
i i ∈ IN b ∈ {0, 1, #}
x# A
#
p
0
p
1
A
s
0
s
1
¢
i y
A w = x#y
• b s
b
y
23
A p
0
p
1
b
• |x| < |y| (q
accept
, N, ¢, N) ∈ δ(p
#
, c, N) c ∈ {0, 1}
• |x| > |y| δ(s
b
, $, d) = {(q
accept
, N, d, N)} b ∈ {0, 1} d ∈ {a, ¢}
A w
2 MT B
L
quad
= {a
n
2
| n ∈ IN
0
}.
w B n
n
|w| = n
2
2
MT B L
quad
B
M = (Q , Σ, Γ, δ, q
0
, q
accept
, q
reject
) HMT x
Σ M
T
M,x
M x
• T
M,x
• T
M,x
0
q
0
¢x M x
• T
M,x
C
C
1
MT 01#01#1 01#0
HKA
HMT
•
24
q
reject
q
accept
q
guess
q
0
q
1
p
0
p
1
s
0
s
1
q
2
p
#
$, a → N, ¢, N
0, ¢ → N, ¢, N
0, ¢ → N, ¢, N
$, a → N, a, N
$, a → N, a, N
1, ¢ → N, ¢, N
1, ¢ → N, ¢, N
1, a → R,
t
, L
1, a → R,
t
, L
1, a → R,
t
, L
0, a → R,
t
, L
0, a → R,
t
, L
0, a → R,
t
, L
#, a → R,
t
, L
#, a → R,
t
, L
0, a → R, a, N0, a → R, a, N
1, a → R, a, N
1, a → R, a, N
1,
t
→ R, a, N
#,
t
→ R, a, N
0,
t
→ R, a, N
¢, ¢ → R, ¢, R
0,
t
→ R, a, R
1,
t
→ R, a, R
#, ¢ → L, ¢, N
0, ¢ → L, ¢, N
1, ¢ → L, ¢, N
$, ¢ → L, ¢, N
$, ¢ → N, ¢, N
$, ¢ → N, ¢, N
#, ¢ → N, ¢, N#, ¢ → R, ¢, N
1, ¢ → R, ¢, N
1, ¢ → R, ¢, N 0, ¢ → R, ¢, N
0, ¢ → R, ¢, N
¢, ¢ → R, ¢, N
• HKA
HMT
M HMT MT A
L(M) = L(A)
M (L(M))
{
A
2
MT A
A A
M
w
A q
0
¢w M
w
A
M A w A
A
M A
A
q
reject
A
A
A
i A
T
M,w
i M i
w ∈ L(M ) C
M w
j ∈ IN C j
j A
w
w /∈ L(M) A w
T
M,x
A q
reject
ut
25
26
q
accept
q
0
q
1
q
2
q
3
q
accept
q
reject
¢ → ¢, R
¢ → ¢, R
0 → 0, R
0 → 0, R
0 → 0, N
0 → 0, N
1 → 1, N
1 → 1, N
1 → 1, N
1 → 1, L
1 → 1, L
A HMT
• 6 T
A
(x) x = 01
x = 0010 5
M
• L(A)
Σ
keyboard
Σ
bool
{0, 1, #}
M = (Q, Σ, Γ, δ, q
0
, q
accept
, q
reject
) MT
Q = {q
0
, q
1
, . . . , q
m
, q
accept
, q
reject
} Γ = { A
1
, A
2
, . . . , A
r
}.
Code(q
i
) = 10
i+1
1 i = 0, 1, . . . , m,
Code(q
accept
) = 10
m+2
1,
Code(q
reject
) = 10
m+3
1,
Code(A
j
) = 110
j
11
j = 1, . . . , r,
Code(N) = 1110111,
Code(R) = 1110
2
111,
Code(L) = 1110
3
111.
Code(δ(p, A
l
) = (q, A
m
, α))
= #Code(p)Code(A
l
)Code(q)Code(A
m
)Code(α)#