Giáo trình môn độ phức tạp tính toán
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (947.95 KB, 49 trang )
∈
k ≥ 3
M = (Q, Σ, Γ, δ, q
0
, B, F )
Q
Σ
Γ Σ
Σ ⊂ Γ
δ
δ : Q × Γ → Q × Γ × {L, R}.
δ(q, X) q ∈ Q, x ∈ Γ (p, Y, D) D
L, R
q
0
q
0
∈ Q
B B ∈ Γ \ Σ
F ⊂ Q
Q
Γ
Σ Σ
∗
X
1
X
2
X
i−1
qX
i
X
i+1
X
n
q
i
X
1
X
2
X
n
X
1
X
n
i
M = (Q, Σ, Γ, δ, q
0
, B, F )
M
M
∗
δ(q, X
i
) = (p, Y, L)
X
1
X
2
X
i−1
qX
i
X
i+1
X
n
M
X
1
X
i−2
pX
i−1
Y X
i+1
X
n
i = 1 X
1
qX
1
X
n
M
pBY X
2
X
n
i = n Y = B B X
n
X
1
X
2
X
n−1
qX
n
M
X
1
X
n−2
pX
n−1
.
δ(q, X
i
) = (p, Y, R)
X
1
X
2
X
i−1
qX
i
X
i+1
X
n
M
X
1
X
2
X
i−1
Y pX
i+1
X
n
i + 1
i = n. i + 1
X
1
X
2
X
n−1
qX
n
X
1
X
2
X
n−1
Y pB.
i = 1 Y = B B X
1
qX
1
X
2
X
n
M
pX
2
X
n
.
{0
n
1
n
, n ≥ 1}.
X Y
M = ({q
0
, q
1
, q
2
, q
3
, q
4
}, {0, 1}, {0, 1, X, Y, B}, δ, q
0
, B, {q
4
})
q
0
(q
1
, X, R) (q
3
, Y, R)
q
1
(q
1
, 0, R) (q
2
, Y, L) (q
1
, Y, R)
q
2
(q
2
, 0, L) (q
0
, X, R) (q
2
, Y, L)
q
3
(q
3
, Y, R) (q
4
, B, R)
q
4
δ(q
0
, 0) = (q
1
, X, R)
δ(q
1
, 0) = (q
1
, 0, R)
δ(q
1
, Y ) = (q
1
, Y, R)
δ(q
1
, 1) = (q
2
, Y, L)
q
0
q
0
0011
q
0
0011 Xq
1
011 X0q
1
11 Xq
2
0Y 1 q
2
X0Y 1
Xq
0
0Y 1 XXq
1
Y 1 XXY q
1
1 XXq
2
Y Y Xq
2
XY Y
XXq
0
Y Y XXY q
3
Y XXY Y q
3
B XXY Y Bq
4
B
0
n
1
n
(n ≥ 1)
X/Y D
X, Y D ←
→
0
n
1
n
M = (Q, Σ, Γ, δ, q
0
, B, F )
L(M) = {W ∈ Σ
∗
| q
0
W
∗
αpβ, p ∈ F, α, β ∈ Γ
∗
}
Σ
∗
Σ
δ(q, X)
M = (Q, {0, 1}, {0, 1, B}, δ, [q
0
, B], {[q
1
, B]})
01
∗
+ 10
∗
.
Q Q = {q
0
, q
1
} × {0, 1, B}
q
0
q
1
q
0
q
1
B
δ
δ([q
0
, B], a) = ([q
1
, a], a, R)
q
0
q
1
δ([q
1
, a], ¯a) = ([q
1
, a], ¯a, R) ¯a a q
1
δ([q
1
, a], B) = ([q
1
, B], B, R)
[q
1
, B]
δ([q
1
, a], a)
[X, Y, Z]
O(n
2
)
§2 δ(q, X)
δ(q, X) {(q
1
, Y
1
, D
1
), (q
2
, Y
2
, D
2
), , (q
k
, Y
k
, D
k
)} k
W ∈ Σ
∗
M
n
M
D
L(M
n
) = L(M
D
).
M
D
M
N
M
N
M
N
×
∗
M
D
L L = L(M)
0
1
00
01
i W
i
{0, 1}
M = (Q, {0, 1}, Γ, δ, B, F )
q
1
, q
2
, , q
r
r
• q
1
q
2
• X
1
, X
2
, , X
s
s X
1
X
2
X
3
• D
1
D
2
δ
δ(q
i
, X
j
) = (q
k
, X
l
, D
m
) i, j, k, l, m
0
i
10
j
10
k
10
l
10
m
i, j, k, l, m ≥ 1
11
C
1
11C
2
11 C
n−1
11C
n
,
C
i
M = ({q
1
, q
2
, q
3
}, {0, 1}, {0, 1, B}, δ, q
1
, B, {q
2
})
δ(q
1
, 1) = (q
3
, 0, R)
δ(q
3
, 0) = (q
1
, 1, R)
δ(q
3
, 1) = (q
2
, 0, R)
δ(q
3
, B) = (q
3
, 1, L)
0100100010100
0001010100100
00010010010100
0001000100010010
⇒
01001000101001100010101001001100010010010100110001000100010010
(M, W )
M W M 111
W
M
i
W
i
i
11001
0 001011101001100 1 W
i
M
i
i, M
i
L(M
i
) ∅
W
i
L
d
W
i
W
i
∈ L(M
i
) M
i
W
i
.
L
d
L
d
L
d
.
L
d
M L
d
{0, 1} M
M i
M = M
i
W
i
L
d
W
i
∈ L
d
M
i
W
i
L
d
,
W
i
∈ L
d
L
d
W
j
M
j
W
j
W
i
∈ L
d
M
i
W
i
L
d
W
i
∈ L
d
W
i
L
d
L
d
M L
d
L
d
L L = L(M)
W ∈ L M
W ∈ L M
L
L
L
u
L
u
(M, W ) M W
0 1 W ∈ L(M)
L
u
U
L
u
= L(U) U
U M
j
L L = L(M)
W
W ∈ L
W ∈ L W
L = L(M) ∀W
W ∈ L M W
W ∈ L M
L
u
L
u
L
d
P
1
P
2
P
1
P
2
P
2
P
1
P
1
P
2
P
1
P
2
P
1
P
2
P
1
P
2
P
1
P
2
P
1
P
2
∃ P
1
P
2
P
1
⇒ P
2
P
1
⇒ P
2
L
e
= {M | L(M) = ∅}
L
ne
= {M | L(M) = ∅}
L
u
L
u
L
u
Σ
A B
A = w
1
, w
2
, , w
k
B = x
1
, x
2
, , x
k
i (w
i
, x
i
)
∃
i
1
, i
2
, , i
m
A B
w
i
1
w
i
2
w
i
m
= x
i
1
x
i
2
x
i
m
.
i
1
, i
2
, , i
m
Σ = {0, 1} A B
A B
i w
i
x
i
1 1 111
2 10111 10
3 10 0
m = 4, i
1
= 2, i
2
=
1, i
3
= 1, i
4
= 3 2, 1, 1, 3
w
2
w
1
w
1
w
3
= x
2
x
1
x
1
x
3
= 101111110
2, 1, 1, 3, 2, 1, 1, 3
Σ = {0, 1}
A B
i w
i
x
i
1 10 101
2 011 11
3 101 011
i
1
, i
2
, , i
m
, m ≥ 1
i
1
= 1 i
1
= 2 w
i
1
w
i
2
w
i
m
0 x
i
1
x
i
2
x
i
m
1 i
1
= 3
i
1
= 1 w
i
1
w
i
2
w
i
m
x
i
1
x
i
2
x
i
m
A B
A : 10
B : 101
i
2
• i
2
= 1 W 1010
X 101101
W X
• i
2
= 2 W = W
1
W
2
= 10011
X = X
1
X
2
= 10111
• i
2
= 3 W = W
1
W
3
= 10101
X = X
1
X
3
= 101011
⇒ i
2
= 3
1, 3
i
3
= 3, i
4
= 3,
A B
A
B
i
1
, i
2
, , i
m
w
1
w
i
1
w
i
2
w
i
m
= x
1
x
i
1
x
i
2
x
i
m
A : 1
B : 111
2 3 w
1
w
3
10
1
A : 11
B : 111111
i
2
= i
3
= = 1
B
A
A B
i w
i
x
i
1 1 111
2 10111 10
3 10 0
Σ
∗
A
∗ Σ B ∗
Σ A B
∗ w
1
($, ∗$)
A B
i w
i
x
i
1 1 111
2 10111 10
3 10 0
⇒
C D
i y
i
z
i
0 ∗1∗ ∗1 ∗ 1 ∗ 1
1 1∗ ∗1 ∗ 1 ∗ 1
2 1∗ 0∗1 ∗1 ∗1∗ ∗1 ∗ 0
3 1 ∗ 0∗ ∗0
4 $ ∗$
L
u
(M, W )
(A, B) M W ⇔ (A, B)
•
•
• M T (n)
T (n) w
n M T (n) M
w
T (n)
• T (n) L = L(M)
M T (n)
