Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
|−−
M
|−−
M
|−−
M
|−−
M
|−−
M
|−−
M
|−−
M
|−−
M
|−−
M
|−−
M
(q
0
, 10110)
(q
1
, 0110)
(q
0
, 0110)
(q
0
, 110)
(q
0
, 10)
(q
1
, 10)
(q
1
, 0)
(q
0
, 0)
(q
2
, 0)
(q
o
, λ)
(q
2
, λ)
{q
0
}
{q
0
}
{q
0
, q
1
}
{q
0
, q
1
}
{q
0
, q
2
}
{q
0
, q
1
, q
2
}
L(M) x11y x y
(Σ
bool
)
∗
M
L(M) = {x11y | x, y ∈ (Σ
bool
)
∗
}.
⊇ {x11y | x, y ∈ (Σ
bool
)
∗
} ⊆ L(M )
w ∈ {x11y | x, y ∈ (Σ
bool
)
∗
} w = x11y x, y ∈ (Σ
bool
)
∗
M
w
q
0
∈ δ(q
0
, 0) ∩ δ(q
0
, 1) M
x ∈ (Σ
bool
)
∗
(q
0
, x)
∗
|−−
M
(q
0
, λ).
q
2
∈ δ(q
2
, 0) ∩δ(q
2
, 1) M
y ∈ (Σ
bool
)
∗
(q
2
, y)
∗
|−−
M
(q
2
, λ).
(q
0
, x11y)
∗
|−−
M
(q
0
, 11y)
|−−
M
(q
1
, 1y)
|−−
M
(q
2
, y)
∗
|−−
M
(q
2
, λ)
M x11y
⊆ L(M) ⊆ {x11y | x, y ∈ (Σ
bool
)
∗
}
w ∈ L(M ) C M
w C w
q
0
q
2
q
0
q
2
q
1
C
(q
0
, w)
∗
|−−
M
(q
1
, z)
∗
|−−
M
(q
2
, λ).
M
q
1
• q
1
/∈ δ(q
1
, a) a ∈ Σ
bool
• M q
1
q
1
C
(q
0
, w)
∗
|−−
M
(q
0
, abu)
|−−
M
(q
1
, bu)
|−−
M
(q
2
, u)
∗
|−−
M
(q
2
, λ),
a, b ∈ Σ
bool
u ∈ Σ
∗
bool
q
1
q
1
∈ δ(q
0
, 1) q
0
1 a = 1 (q
1
, 0) = ∅ δ(q
1
, 1) =
{q
2
} q
1
1 b = 1
C
(q
0
, w)
∗
|−−
M
(q
0
, 11u)
|−−
M
(q
1
, 1u)
|−−
M
(q
2
, u)
∗
|−−
M
(q
2
, λ).
w 11
w ∈ {x11y | x, y ∈ (Σ
bool
)
∗
}.
ut
{1011x00y | x, y ∈ (Σ
bool
)
∗
}
{01, 101}
∗
{x ∈ (Σ
bool
)
∗
| x 01011 01100}
{x ∈ (Σ
10
)
∗
| Number
10
(x) 3}
HKA
L(HKA) = {L(M ) | M HKA}.
L(HKA) = L(KA)
30
a b 1
M
A
M
i
i
i i
M
i ∈ IN
0
i
u v
u v
HKA M
x i ∈ {0, 1 , . . . , |x|}
i M x
i
ˆ
δ(q
0
, z)
z x
i
ˆ
δ(q
0
, 10) = {q
0
}
ˆ
δ(q
0
, 101) = {q
0
, q
1
}
ˆ
δ(q
0
, 1011) = {q
0
, q
1
, q
2
}
ˆ
δ(q
0
, 10110) = {q
0
, q
2
}
i = 0, 1, . . . , 5
i
i
qq
B
M
(x) :
T
q
T
q
Q
HKA M = (Q, Σ, δ, q
0
, F )
A A
hP i A P ⊆ Q
P
M z P =
ˆ
δ(q
0
, z) A hP i
a
[
p∈P
δ(p, a)
a M P
HKA M
A
L(M) = L(A).
M = (Q, Σ, δ
M
, q
0
, F ) HKA
A = (Q
A
, Σ
A
, δ
A
, q
0A
, F
A
)
• Q
A
= {hP i | P ⊆ Q}
• Σ
A
= Σ
• q
0A
= h{q
0
}i
• F
A
= {hP i | P ⊆ Q P ∩ F 6= ∅}
• δ
A
Q
A
× Σ
A
Q
A
hP i ∈ Q
A
a ∈ Σ
A
δ
A
(hP i, a) =
*
[
p∈P
δ
M
(p, a)
+
= h{q ∈ Q | ∃p ∈ P,
q ∈ δ
M
(p, a)}i.
A
A HKA
M
A
HKA M x ∈ Σ
∗
ˆ
δ
M
(q
0
, x) = P ⇐⇒
ˆ
δ
A
(q
0A
, x) = hP i.
|x|
|x| = 0 x = λ
ˆ
δ
M
(q
0
, λ) = {q
0
}
q
0A
= h{q
0
}i
x = λ
31
hP i P
hP i A P M
P
32
33
h∅i h{q
1
}i h{q
2
}i h{q
1
, q
2
}i A
h{q
0
}i
A
A
h{q
0
}i
h{q
1
}i
h{q
2
}i
h∅i
h{q
0
, q
1
}i
h{q
0
, q
2
}i
h{q
1
, q
2
}i
h{q
0
, q
1
, q
2
}i
0
0
0
0
0
0, 1
0, 1
0, 1
1
1
1
1
1
m ∈ IN
0
z ∈ Σ
∗
|z| ≤ m
Σ
m+1
y Σ
m+1
y = xa x ∈
Σ
m
a ∈ Σ
ˆ
δ
A
ˆ
δ
A
(q
0A
, xa) = δ
A
(
ˆ
δ
A
(q
0A
, x), a).
x
ˆ
δ
A
(q
0A
, x) = hRi ⇔
ˆ
δ
M
(q
0
, x) = R
ˆ
δ
A
(q
0A
, x) =
D
ˆ
δ
M
(q
0
, x)
E
.
A δ
A
R ⊆ Q a ∈ Σ
δ
A
(hRi, a) =
*
[
p∈R
δ
M
(p, a)
+
.
ˆ
δ
A
(q
0A
, xa) =
(3.12)
δ
A
(
ˆ
δ
A
(q
0A
, x), a)
=
(3.13)
δ
A
(
D
ˆ
δ
M
(q
0
, x)
E
, a)
=
(3.14)
*
[
p∈
ˆ
δ
M
(q
0
,x)
δ
M
(p, a)
+
=
D
ˆ
δ
M
(q
0
, xa)
E
.
ut
A B
L(A) = L (B)
HKA
q
0
q
1
q
2
q
k−1
q
k
0, 1
00
0 0
111
1
1
. . .
. . .
L(KA) = L(HKA)
HKA
k
L
k
= {x1y | x ∈ (Σ
bool
)
∗
, y ∈ (Σ
bool
)
k−1
}.
A
k
L
k
q
0
1
k A
k
A
k
A
k
L
k
k
B
k
L
k
= L(B
k
)
A
k
k + 1
L
k
A
k
k ∈ IN
L
k
2
k
B
k
= (Q
k
, Σ
bool
, δ
k
, q
0k
, F
k
)
L(B
k
) = L
k
B
k
2
k
ˆ
δ
k
(q
0k
, x) =
ˆ
δ
k
(q
0k
, y)
x y Σ
bool
z ∈ (Σ
bool
)
∗
xz ∈ L(B
k
) ⇐⇒ yz ∈ L(B
k
).
S
k
x, y ∈ S
k
z
xz ∈ L(B
k
) yz /∈ L(B
k
).
B
k
|S
k
|
S
k
= (Σ
bool
)
k
u ∈ S
k
ˆ
δ
k
(q
0k
, u)
34
L
k
2
k
35
|S
k
|
x = x
1
x
2
. . . x
k
y = y
1
y
2
. . . y
k
,
S
k
= (Σ
bool
)
k
x
i
y
i
∈ Σ
bool
i = 1, . . . , k
ˆ
δ
k
(q
0k
, x) =
ˆ
δ
k
(q
0k
, y).
x 6= y j ∈ {1, . . . , k} x
j
6= y
j
x
j
= 1 y
j
= 0.
z = 0
j−1
xz = x
1
. . . x
j−1
1x
j+1
. . . x
k
0
j−1
, yz = y
1
. . . y
j−1
0y
j+1
. . . y
k
0
j−1
xz ∈ L
k
yz /∈ L
k
.
ˆ
δ
k
(q
0k
, x)
ˆ
δ
k
(q
0k
, y)
B
k
|S
k
| = 2
k
ut
L = {x11y | x, y ∈ {0, 1 }
∗
},
L
3 3
λ, 1, 11.
(x, y) S = {λ, 1, 11}
z xz yz
L x y
x = λ y = 1 z = 1
xz = 1 /∈ L yz = 1 1 ∈ L
ˆ
δ(q
0
, x) 6=
ˆ
δ(q
0
, y)
L
x = λ y = 11 z = 0
xz = 0 /∈ L yz = 110 ∈ L.
x = 1 y = 11 z = λ
xz = 1 /∈ L yz = 11 ∈ L.
ˆ
δ(q
0
, λ),
ˆ
δ(q
0
, 1)
ˆ
δ(q
0
, 11)
A = (Q, Σ
bool
, δ, q
0
, F ) L
L = {x11y | x, y ∈ {0, 1}
∗
} S = {λ, 1, 11}
x, y S Z(x, y) ⊆ (Σ
bool
)
∗
z ∈ Z(x, y)
(xz /∈ L yz ∈ L) (xz ∈ L yz /∈ L).
L =
{x11y | x, y ∈ { 0, 1}
∗
}
3 3
λ 1 11
L = {x011y | x, y ∈ {0, 1}
∗
}
• M L 4
L = L(M)
• M 3
L(M) = L
•
L
∗
A
L(A)
L(A)
HKA 6 L(M) =
{0x | x ∈ {0, 1}
∗
x 11 100
}
C D
C D
x
x
L /∈ L(KA) L
Σ
∗
L
x
(Σ, L)
A (Σ, L)
x ∈ L
y /∈ L A y
A B
B A
B
A
B z A
z
B A
36
37
0