Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
q
0
q
1
q
A
q
B
q
reject
q
accept
q
even
q
right
q
left
q
middle
q
odd
1 → 1, R
1 → 1, R
1 → 1, R
0 → 0, R
0 → 0, R
0 → 0, R
¢ → ¢, R
¢ → ¢, R
¢ → ¢, R
t
→
t
, L
0 → 0, L
0 → 0, L
1 → 1, L
1 → 1, L
t
→
t
, N
t
→
t
, N
0 → 0, N
1 → 1, N
0 →
0
B
, L
1 →
1
B
, L
0
A
→
0
A
, R
0
A
→
0
A
, R
1
A
→
1
A
, R
1
A
→
1
A
, R
1
B
→ 1, N
0 →
0
A
, R
1 →
1
A
, R
0
B
→
0
B
, L
1
B
→
1
B
, L
0
B
→ 0, N
a b
X
M x = 1001101
x
q
0
¢1001101
|−−
M
¢q
even
1001101
|−−
M
¢1q
odd
001101
|−−
M
¢10q
even
01101
|−−
M
¢100q
odd
1101
|−−
M
¢1001q
even
101
|−−
M
¢10011q
odd
01
|−−
M
100110q
even
1
|−−
M
¢1001101q
oddt
|−−
M
¢100110q
B
1
q
B
x
M a
a
B
a
A
¢100110q
B
1
|−−
M
¢10011q
1
0
1
B
|−−
M
¢1001q
left
10
1
B
|−−
M
¢100q
left
110
1
B
|−−
M
¢10q
left
0110
1
B
|−−
M
¢1q
left
00110
1
B
|−−
M
¢q
left
100110
1
B
|−−
M
q
left
¢100110
1
B
|−−
M
¢q
A
100110
1
B
|−−
M
¢
1
A
q
right
00110
1
B
|−−
M
¢
1
A
0q
right
0110
1
B
∗
|−−
M
¢
1
A
00110q
right
1
B
|−−
M
¢
1
A
0011q
B
0
1
B
|−−
M
¢
1
A
001q
1
1
0
B
1
B
|−−
M
¢
1
A
00q
left
11
0
B
1
B
∗
|−−
M
¢q
left
1
A
0011
0
B
1
B
|−−
M
¢
1
A
q
A
0011
0
B
1
B
|−−
M
¢
1
A
0
A
q
right
011
0
B
1
B
∗
|−−
M
¢
1
A
0
A
011q
right
0
B
1
B
|−−
M
¢
1
A
0
A
01q
B
1
0
B
1
B
|−−
M
¢
1
A
0
A
0q
1
1
1
B
0
B
1
B
∗
|−−
M
¢
1
A
q
left
0
A
01
1
B
0
B
1
B
|−−
M
¢
1
A
0
A
q
A
01
1
B
0
B
1
B
|−−
M
¢
1
A
0
A
0
A
q
right
1
1
B
0
B
1
B
|−−
M
¢
1
A
0
A
0
A
1q
right
1
B
0
B
1
B
|−−
M
¢
1
A
0
A
0
A
q
B
1
1
B
0
B
1
B
|−−
M
¢
1
A
0
A
q
1
0
A
1
B
1
B
0
B
1
B
|−−
M
¢
1
A
0
A
0
A
q
middle
1
B
1
B
0
B
1
B
|−−
M
¢
1
A
0
A
0
A
q
accept
1
1
B
0
B
1
B
.
MT q
accept
1 MT 100 1101
M
010011 101
M
M M
0
L(M
0
) = {w ∈ {0, 1}
∗
| w = x1x x ∈ {0, 1}
∗
}.
L
P
= {0
2
n
| n ∈ IN}
L
¢
t
0
0 a 0
q
reject
t
¢ 0 1
• 0
q
reject
q
accept
q
0
q
1
q
2
q
3
q
even
q
odd
¢ → ¢, N
¢ → ¢, N
0 → a, R
t
→
t
, L
t
→
t
, L
0 → 0, R
0 → 0, L
0 → 0, L
0 → 0, L
a → a, Ra → a, R
a → a, L
a → a, L
a → a, L
¢ → ¢, R
¢ → ¢, R
• 0
i 2
i
2
1
A = ({q
0
, q
even
, q
odd
, q
1
, q
2
, q
3
, q
accept
, q
reject
} {0} {0, a, ¢,
t
}, δ
A
, q
0
, q
accept
, q
reject
)
δ
A
L
P
i = 2j
0
i
0
j
1
j
j
0
j
1
j
0
j
2
1
j
2
1
j
01
i−1
L
P
• {a
n
b
n
| n ∈ IN
0
}
• {0
n
2
| n ∈ IN
0
}
• {w#w | w ∈ {0, 1}
∗
}
• {x#y | x, y ∈ {0, 1}
∗
, Number (x) = Number (y) + 1}
x ∈ (Σ
bool
)
∗
q
accept
• y ∈ (Σ
bool
)
∗
Number (y) = Number (x) + 1
• x#x
• z ∈ (Σ
bool
)
∗
Number (z) = 2 · Number (x)
• ###x
k
k
•
•
• k
w k
• ¢w$ ¢ $
11
12
13
¢
¢
¢
¢
$
w
tt
tt
tt
···
···
···
1
2
k
• ¢
• ¢
ttt
. . .
¢
• q
0
¢
$
¢w$
w
Γ
k + 1 0
¢
k
(q, w, i, u
1
, i
1
, u
2
, i
2
, . . . , u
k
, i
k
)
Q × Σ
∗
× IN
0
× (Γ
∗
× IN
0
)
k
.
M
• M q
• ¢w$ i
w = a
1
a
2
. . . a
n
a
i
∈ Σ
a
i
• j ∈ {1, 2, . . . , k} j ¢u
j ttt
. . .
i
j
≤ |u
j
| j
M
δ : Q × (Σ ∪ {¢, $}) × Γ
k
→ Q ×{L, R, N} × (Γ × {L, R, N})
k
.
(q, a, b
1
, . . . , b
k
) ∈ Q ×(Σ ∪ {¢, $}) × Γ
k
• q
• a ∈ Σ ∪ {¢, $}
• k b
1
, . . . , b
k
k
M
• k b
1
, . . . , b
k
• M
• k + 1
M w q
accept
M w M w M w
q
reject
M w
M q
reject
w
k
k
k
k MT k MT
MMT MMT
MT
L
equal
= {w#w | w ∈ (Σ
bool
)
∗
}.
x#y MT x
# y #
1 MT A L
equal
¢ ¢
¢
¢
$ $
x
xx ## yy
t
···
···
A x#y x, y ∈ (Σ
bool
)
∗
A
x#y A x
¢x
A ¢
# A
x y
A x 6= y
t
A
qp
a, b → X, d, Y
δ(p, a, b) = (q, X, d, Y)
1 MT p
q a
b b d X ∈ {L, R, N}
Y ∈ {L , R, N}
1
MT L
equal
q
0
, q
1
, q
2
q
reject
# M q
2
M
q
reject
q
2
¢ q
copy
M
14
A #
# q
adjust
¢
x y x#y q
compare
x = y
M q
accept
x y
q
reject
q
reject
q
accept
q
compare
q
adjust
q
copy
q
0
q
1
q
2
1, ¢ → R, ¢, N
1, ¢ → R, ¢, N
0, ¢ → R, ¢, N
0, ¢ → R, ¢, N
¢, ¢ → R, ¢, N
$, ¢ → N, ¢, N
#, ¢ → R, ¢, N
#, ¢ → N, ¢, N
$, ¢ → L, ¢, N
1,
t
→ R, 1, R
0,
t
→ R, 0, R
¢, ¢ → R, ¢, R
#,
t
→ N,
t
, L
#, 0 → N, 0, L
#, 1 → N, 1, L
0, 0 → R, 0, R
1, 1 → R, 1, R
#, ¢ → R, ¢, R
$,
t
→ N,
t
, N
1, 0 → N, 0, N
0, 1 → N, 1, N
$, 0 → N, 0, N
$, 1 → N, 1, N
1, ¢ → L, ¢, N
0, ¢ → L, ¢, N
#, ¢ → L, ¢, N
0,
t
→ N,
t
, N
1,
t
→ N,
t
, N
1
• L = {a
n
b
n
| n ∈ IN
0
}
• L = {w ∈ (Σ
bool
)
∗
| |w|
0
= |w|
1
}
• L = {a
n
b
n
c
n
| n ∈ IN
0
}
• L = {www | w ∈ (Σ
bool
)
∗
}
• L = {a
n
2
| n ∈ IN
0
}
A B
Σ
A B x ∈ (Σ
bool
)
∗
• A x B x
• A x B x
• A x
B x
A B L(A) = L(B)
L(A) = L (B) A B
A 1
MT B A B
A B
B 1 MT B
B w
B A w
B
A
A B ut
1 MT B
MT A = (Q, Σ, Γ, δ, q
0
, q
accept
, q
reject
)
L(A) = L (B) A B
A
B A B
15
A k MT
B A
A
B
A
wwA B
¢
¢
¢
¢
¢
¢
¢
¢
¢
$
$
x
1
x
1
x
2
x
2
x
k
x
k
↑
↑
↑
↑
. . .
t
t t
tt
t t
tt ttt
ttt
ttt
ttt
A B
B k + 1
A B
2(k + 1)
A
Γ
A
A
B
Γ
B
= (Σ ∪ {¢, $,
t
}) × {
t
, ↑} ×(Γ
A
× {
t
, ↑})
k
∪Σ
A
∪{¢}.
α = (a
0
, a
1
, a
2
, . . . , a
2k+1
) ∈ Γ
B
a
i
i i
B i
(q, w, i, x
1
, i
1
, x
2
, i
2
, . . . , x
k
, i
k
)