Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
•
ˆ
δ(q, λ) = q q ∈ Q
•
ˆ
δ(q, wa ) = δ(
ˆ
δ(q, w), a) a ∈ Σ w ∈ Σ
∗
q ∈ Q
(q, w)
∗
|−−
M
(p, u)
M
(q, w) (p, u)
ˆ
δ(q, w) = p
• M q w
• M p
ˆ
δ(q, w) = p
(q, w)
∗
|−−
M
(p, λ).
L(M)
L(M) = {w ∈ Σ
∗
| (q
0
, w)
∗
|−−
M
(p, λ) p ∈ F }
= {w ∈ Σ
∗
|
ˆ
δ(q
0
, w) ∈ F }.
M L(M)
M 1 q
0
q
2
q
1
q
3
0
x
ˆ
δ(q
0
, x) ∈ {q
0
, q
1
}
ˆ
δ(q
0
, x) ∈ {q
2
, q
3
}
L(M) = {w ∈ {0, 1}
∗
| |w|
0
+ |w|
1
≡ 0 (mod 2)}
Σ
∗
|Q|
Kl = {w ∈ Σ
∗
|
ˆ
δ(q
0
, w) = p},
= {w ∈ Σ
∗
| (q
0
, w)
|−−
M
(p, x)},
p, q ∈ Q p 6= q
[
p∈Q
Kl[p] = Σ
∗
Kl[p] ∩ Kl[q] = ∅.
L(M)
L(M) =
[
p∈F
Kl[p].
xR
δ
y ⇔
ˆ
δ(q
0
, x) =
ˆ
δ(q
0
, y),
Kl(q
0
)
Kl(q
1
)
Kl(q
2
)
Kl(q
3
)
Kl(q
n
)
∗
Σ
∗
Kl[p]
L(M)
M Kl[q
0
] Kl[q
1
] Kl[q
2
] Kl[q
3
]
Kl[q
0
] = {w ∈ {0, 1}
∗
| |w|
0
|w|
1
};
Kl[q
1
] = {w ∈ {0, 1}
∗
| |w|
0
|w|
1
};
Kl[q
2
] = {w ∈ {0, 1}
∗
| |w|
0
|w|
1
};
Kl[q
3
] = {w ∈ {0, 1}
∗
| |w|
0
|w|
1
}.
Kl[q
0
] ∪ Kl[q
3
] = {w ∈ {0, 1}
∗
| |w|
0
+ |w|
1
≡ 0 (mod 2)},
2
ˆ
δ(q
0
, λ) = q
0
⇒ λ ∈ Kl[q
0
].
ˆ
δ(q
0
, 1) = q
1
⇒ 1 ∈ Kl[q
1
].
ˆ
δ(q
0
, 0) = q
2
⇒ 0 ∈ Kl[q
2
].
(q
0
, 00)
|−−
M
(q
2
, 0)
|−−
M
(q
0
, λ) ⇒ 00 ∈ Kl[q
0
].
(q
0
, 01)
|−−
M
(q
2
, 1)
|−−
M
(q
3
, λ) ⇒ 01 ∈ Kl[q
3
].
(q
0
, 10)
|−−
M
(q
1
, 0)
|−−
M
(q
3
, λ) ⇒ 10 ∈ Kl[q
3
].
(q
0
, 11)
|−−
M
(q
1
, 1)
|−−
M
(q
0
, λ) ⇒ 11 ∈ Kl[q
0
].
0 1 2
i ≥ 2
x ∈ {0, 1}
∗
|x| ≤ i
i + 1
i ≥ 2
(Σ
bool
)
∗
w (Σ
bool
)
i+1
w
w = za z ∈ Σ
i
a ∈ Σ |z|
0
|z|
1
|z|
0
|z|
1
|z|
0
|z|
1
|z|
0
|z|
1
|z|
0
|z|
1
z |z| =
i
ˆ
δ(q
0
, z) = q
0
z ∈ Kl[q
0
]
ˆ
δ(q
0
, za) = δ(
ˆ
δ(q
0
, z), a) =
δ(q
0
, a) =
q
1
,
a = 1,
q
2
, a = 0.
|z1|
0
|z1|
1
ˆ
δ(q
0
, z1) = q
1
z1 ∈ Kl[q
1
]
|z0|
0
|z0|
1
ˆ
δ(q
0
, z0) =
q
2
z0 ∈ Kl[q
2
]
z
ˆ
δ(q
0
, z) = q
3
z ∈ Kl[q
3
]
ˆ
δ(q
0
, za) = δ(
ˆ
δ(q
0
, z), a) =
δ(q
3
, a) =
q
2
,
a = 1,
q
1
, a = 0.
z0 ∈ Kl[q
1
] z1 ∈ K l[q
2
]
ut
ˆ
δ
∗
|−−
M
|−−
M
ˆ
δ
L = {w ∈ (Σ
bool
)
∗
| |w|
0
} M
L(M) = L
∅, Σ
∗
Σ
+
Σ
A
L(A)
Σ
∗
Σ
U = {w ∈ (Σ
bool
)
∗
| |w|
0
= 3 (|w|
1
≥ 2 |w|
1
= 0)}.
|w|
0
= 3 w B
L(B) = U
|w|
0
= 0, |w|
0
= 1, |w|
0
= 2, |w|
0
= 3 |w|
0
≥ 4
B 0 4
1
|w|
1
= 0, |w|
1
= 1 |w|
1
≥ 2.
{0, 1}
∗
Q = {q
i,j
| i ∈ {0 , 1, 2, 3, 4}, j ∈ {0, 1, 2}}.
i ∈ { 0, 1, 2, 3} j ∈ {0, 1}
Kl[q
i,j
] = {w ∈ (Σ
bool
)
∗
| |w|
0
= i |w|
1
= j};
Kl[q
i,2
] = {w ∈ (Σ
bool
)
∗
| |w|
0
= i
|w|
1
≥ 2};
Kl[q
4,j
] = {w ∈ (Σ
bool
)
∗
| |w|
0
≥ 4
|w|
1
= j};
Kl[q
4,2
] = {w ∈ (Σ
bool
)
∗
| |w|
0
≥ 4
|w|
1
≥ 2}.
B q
0,0
B q
i,j
U = Kl[q
3,0
] ∪ K l[q
3,2
],
F = {q
3,0
, q
3,2
}
11
12
Kl[q
i,j
]
q
0,0
q
0,1
q
0,2
q
1,0
q
1,1
q
1,2
q
2,0
q
2,1
q
2,2
q
3,0
q
3,1
q
3,2
q
4,0
q
4,1
q
4,2
0
0
00 00
00 00
00 00
1
1
1
1
111 11
111 11
0, 1
B
• L(B) = U
• A L(A) = U A
B Kl[q] q A
• {w ∈ {0, 1, 2}
∗
| w = 002122x, x ∈ (Σ
bool
)
∗
}
• {w ∈ {a, b, c}
∗
| w = xabcabc, x ∈ {a, b, c}
∗
}
• {w ∈ {a, b, c}
∗
| w = xaabby, x, y ∈ {a, b, c}
∗
• {w ∈ {0, 1}
∗
| |w|
0
≡ 1 (mod 3 ) w = x111y x, y ∈ {0, 1}
∗
}
• {abbxb
3
y | x, y ∈ {a , b}
∗
}
• {w ∈ {a, b}
∗
| w = abbz w = ub
3
v z, u, v ∈ {a, b}
∗
}
Kl[q]
q
x
2
x
2
x
2
x
1
x
1
x
1
x
i
x
i
x
i
M
1
: M
2
:
M :
(q, p)
q p
Σ M
1
= (Q
1
, Σ, δ
1
, q
01
, F
1
) M
2
=
(Q
2
, Σ, δ
2
, q
02
, F
2
)
∈ {∪, ∩, −} M
L(M) = L(M
1
) L(M
2
).
M
M
1
M
2
M (q, p) q
M
1
p M
2
q
M
1
q
M p M
2
p
M M
M
1
M
2
M M = (Q, Σ, δ, q
0
, F
)
• Q = Q
1
× Q
2
13
M M
M
1
M
2
• q
0
= (q
01
, q
02
)
• q ∈ Q
1
p ∈ Q
2
a ∈ Σ δ((q , p), a) = (δ
1
(q, a), δ
2
(p, a))
• = ∪ F = F
1
× Q
2
∪ Q
1
× F
2
{
M
1
M
2
}
= ∩ F = F
1
× F
2
{
}
= − F = F
1
× (Q
2
− F
2
)
{M
1
M
2
}
L(M) = L(M
1
) L(M
2
)
∈ {∪, ∩, −}
ˆ
δ((q
01
, q
02
), x) = (
ˆ
δ
1
(q
01
, x),
ˆ
δ
2
(q
02
, x))
x ∈ Σ
∗
|x|
x = λ
i
x ∈ Σ
∗
|x| ≤ i
w ∈ Σ
i+1
x w
w Σ
i+1
w
w = za z ∈ Σ
i
a ∈ Σ.
ˆ
δ
ˆ
δ((q
01
, q
02
), w) =
ˆ
δ((q
01
, q
02
), za)
= δ(
ˆ
δ((q
01
, q
02
), z), a)
=
(3.1)
δ((
ˆ
δ
1
(q
01
, z),
ˆ
δ
2
(q
02
, z)), a)
=
δ
(δ
1
(
ˆ
δ
1
(q
01
, z), a), δ
2
(
ˆ
δ
2
(q
02
, z), a))
= (
ˆ
δ(q
01
, za),
ˆ
δ (q
02
, za))
= (
ˆ
δ(q
01
, w),
ˆ
δ(q
02
, w)).
ut
L ⊆ Σ
∗
L
{
=
Σ
∗
− L
L
L
M
L
A x
y
ˆ
δ(q
0
, x) =
ˆ
δ(q
0
, y)
A
x y
ˆ
δ(q
0
, x) =
ˆ
δ(q
0
, y)
z ∈ Σ
∗
ˆ
δ
A
(q
0
, xz) =
ˆ
δ
A
(q
0
, yz).
A = (Q, Σ, δ
A
, q
0
, F )
x, y ∈ Σ
∗
x 6= y
p ∈ Q
(q
0
, x)
∗
|−−
A
(p, λ)
(q
0
, y)
∗
|−−
A
(p, λ)
ˆ
δ
A
(q
0
, x) =
ˆ
δ
A
(q
0
, y) = p
x, y ∈ Kl[p]
z ∈ Σ
∗
r ∈ Q xz, yz ∈ Kl[r]
xz ∈ L(M) ⇐⇒ yz ∈ L(M ).
(q
0
, x)
∗
|−−
A
(p, λ) (q
0
, y)
∗
|−−
A
(p, λ)
A x y z ∈ Σ
∗
xz yz
14
15
(q
0
, xz)
∗
|−−
A
(p, z) (q
0
, yz)
∗
|−−
A
(p, z).
r =
ˆ
δ
A
(p, z) (p, z)
∗
|−−
A
(r, λ) A z
p A xz
(q
0
, xz)
∗
|−−
A
(p, z)
∗
|−−
A
(r, λ),
A yz
(q
0
, yz)
∗
|−−
A
(p, z)
∗
|−−
A
(r, λ).
r ∈ F xz yz L(A) r /∈ F
L(A) ut
L = {0
n
1
n
| n ∈ IN
0
}.
L
0
n
L
L /∈ L(KA)
L ∈ L(KA) A = (Q, Σ
bool
, δ
A
, q
0
, F )
L(A) = L
0
1
, 0
2
, 0
3
, . . . , 0
|Q|+1
.
|Q| + 1 i, j ∈ {1, 2, . . . , |Q| + 1}
i < j
ˆ
δ
A
(q
0
, 0
i
) =
ˆ
δ
A
(q
0
, 0
j
).
0
i
z ∈ L ⇔ 0
j
z ∈ L
z ∈ (Σ
bool
)
∗
z = 1
i
0
i
1
i
∈ L
0
j
1
i
/∈ L
16
L(KA)
• {w ∈ {a, b}
∗
| |w|
a
= |w|
b
}
• {a
n
b
m
c
n
| n , m ∈ IN
0
}
• {w ∈ {0, 1, #}
∗
| w = x#x x ∈ {0, 1}
∗
}
• {x1y ∈ {0, 1}
∗
| |x| = |y|}
L /∈ L(KA)
(p, x)
∗
|−−
A
(p, λ),
p x
(p, x
i
)
∗
|−−
A
(p, λ)
i A
x A
x
ˆ
δ
A
(q
0
, y) = p
y ∈ Σ
∗
ˆ
δ
A
(p, z) = r
z ∈ Σ
∗
(q
0
, yx
i
z)
∗
|−−
A
(p, x
i
z)
∗
|−−
A
(p, z)
∗
|−−
A
(r, λ)
A yx
i
z i ∈ IN
0
{yx
i
z | i ∈ IN
0
} ⊆ Kl[r]
r ∈ Q A yx
i
z
i ∈ IN
0
r ∈ F r ∈ Q−F
L n
0
∈ IN
w ∈ Σ
∗
|w| ≥ n
0
w = yxz,
|yx| ≤ n
0
|x| ≥ 1
{yx
k
z | k ∈ IN
0
} ⊆ L {yx
k
z | k ∈ IN
0
} ∩ L = ∅
17