Морозов А.С. Введение в вычислимость
Подождите немного. Документ загружается.
A
∗
w ∈ T (A
∗
) T (A)
∗
w = Λ
w 6= Λ
A
∗
w
w = w
0
w
1
. . . w
k
w
i
i 6= 0
w
i
T (A)
w
0
∈ T (A)
A
A
w
i
i = 1, . . . , k
a q
A
a
q
A w
i
w
i
∈ T (A)
w = w
0
w
1
. . . w
k
∈ T (A)
∗
T (A)
∗
⊆ T (A
∗
)
¤
∅ {Λ} {a}
¤
L
n w ∈ L
w = w
0
w
0
w
1
|w
0
| > n
w
0
= αβγ β 6= Λ k = 0, 1, 2, . . .
w
0
αβ
k
γw
1
∈ L
L A
n w ∈ L
w
w
0
n
q
w
w
0
w
0
q
w
0
q
w
0
w
1
α
β 6= Λ γ
k
w
0
αβ
k
γw
1
w
0
αβ
k
γw
1
∈ L
L = {a
m
b
m
| m ∈ N} n
a
m
b
m
∈ L
n < m a
m+k
b
m
k > 0 L
L = {a
m
b
m
| m ∈ N}
A
a ∈ A
∅ Λ
α β (αβ) (α ∪ β) (α
∗
)
∗
αβ ∪
αβ
∗
∪ β ((α(β
∗
)) ∪ β)
L
A A
L(Λ) = {Λ}
L(∅) = ∅
L(a) = {a}; ( a ∈ A)
L(αβ) = L(α)L(β)
L(α ∪ β) = L(α ) ∪ L(β)
L(α
∗
) = L(α)
∗
.
L A
α A L =
L(α)
( ) A
α
α a ∅ Λ L(α)
{a} ∅ {Λ}
α
β
α L(β)
α = βγ
L(α) = L(β)L(γ)
L(β) L(γ) L(α)
α = β ∪ γ
α = β
∗
A q
1
, . . . , q
n
i, j, k 1 6 i, j 6 n 0 6 k 6 n
R(i, j, k)
A q
i
q
j
q
k+1
, q
k+2
, . . .
R(i, j, n)
A q
i
q
j
q
1
T (A) =
[
q
j
∈F
R(1, j, n).
R(i, j, k)
1 6 i, j 6 n 0 6 k 6 n
k = 0 R(i, j, k)
q
i
q
j
k− 1
R(i, j, k)
q
i
q
k
q
j
q
i
→ . . . → q
k
→ . . . → q
k
→ . . . → q
k
→ . . . → q
j
.
q
k
R(i, j, k −1) q
k
k q
i
q
j
q
i
→ . . . → q
k
R(i, k, k−1)
R(k, k, k−1)
R(k, j, k −1)
R(i, j, k) = R(i, j, k − 1) ∪ R(i, k, k − 1)R(k, k, k − 1)
∗
R(k, j, k −1).
R(i, j, k−1) = L(α)
R(i, k, k −1) = L(β) R(k, k, k −1) = L(γ) R(k, j, k −1) = L(δ) R(i, j, k) =
α ∪ βγ
∗
δ
¤
∗
L L
0
=
{w
0
| w ∈ L} w
0
w
L
L
0
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
0 1, 2, 3, 4, 5, 6, 7, 8, 9
Λ
0 1 2 3 4 5 6 7 8 9 0
h i → 0
h i → 1 h i
h i → 2 h i
···
h i → 9 h i
h i → Λ
h i → 0 h i
h i → 1 h i
···
h i → 9 h i.
h i
→
h i → 3 h i →
→ 30 h i →
→ 308 h i →
→ 308 (= 308Λ).
h i
x, y
( ) + − × /
x y
v
w
(v + w) (v − w) (v × w) (v/w)
h i → h i
h i → x
h i → y
h i → (h i + h i)
h i → (h i − h i)
h i → (h i × h i)
h i → (h i/ h i)
(x × (y + 20))
h i → (h i × h i) →
→ (x × h i) →
→ (x × (h i + h i)) →
→ (x × (y + h i)) →
→ (x × (y + h i)) →
→ (x × (y + 2 h i)) →
→ (x × (y + 20 h i))
→ (x × (y + 20)) ( = (x × (y + 20Λ)) ).
h i
Γ = (V, T, P, S)
• V
• T
V ∩ T = ∅
• P α → β
α ∈ (V ∪T )
+
β ∈ (V ∪T )
∗
α
V
• S V
V = {h i, h i, h i},
S = h i
T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, (, ), +, −, ×, / }.
Γ = (V, T, P, S)
α β (V ∪ T )
∗
Γ β α
α
→
Γ
β α
0
α
1
γ δ α = α
0
γα
1
β = α
0
δα
1
(γ → δ ) ∈ P α
γ δ Γ
β
α Γ
k β
0
, . . . , β
k−1
α
→
Γ
β
0
→
Γ
β
1
→
Γ
. . .
→
Γ
β
k−1
→
Γ
β;
α
∗
→
Γ
β
β α α
→
Γ
β α
∗
→
Γ
β
Γ = (V, T, P, S)
L(Γ) =
(
β ∈ T
∗
¯
¯
¯
¯
¯
S
∗
→
Γ
β
)
.
L(Γ) Γ
S
• α → β
|α| ≤ |β|
• A → β
A V
•
A → aB A → a A, B ∈ V a ∈ T
Λ
Λ
A T (A)\{Λ}
L
Γ = (V, T, P, S)
A
Γ
V
Q
S
T A
Γ
a A ∈ V B ∈ V
P A → aB
a A ∈ V
Q P A → a
L(Γ) = T (A
Γ
) w = a
0
a
1
. . . a
s
∈ L(Γ)
S
→
Γ
a
0
A
0
→
Γ
a
0
a
1
A
1
→
Γ
. . .
→
Γ
a
0
a
1
. . . a
s−1
A
s−1
→
Γ
a
0
a
1
. . . a
s−1
a
s
= w.
P
S → a
0
A
0
A
0
→ a
1
A
1
. . .
A
s−2
→ a
s−1
A
s−1
A
s−1
→ a
s
.
A
Γ
S Q
S
a
0
−→ A
0
a
1
−→ A
1
a
2
−→ . . . A
s−1
a
s
−→ Q.