Морозов А.С. Введение в вычислимость
Подождите немного. Документ загружается.
w = a
0
a
1
. . . a
s
∈ T (A
Γ
)
w w ∈ L(Γ) ⇔ w ∈ T (A
Γ
) L(Γ) =
T (A
Γ
)
A
Γ L(Γ) = T (A) \ {Λ}
A
A
0
T (A
0
) = T (A) \ {Λ} Γ = (V, T, S, P )
V A
0
S A → aB
P A
0
A B
a A → a
P A
0
A
B a
L(Γ) = T (A
0
) w = a
1
. . . a
k
∈
L(Γ)
S
→
Γ
a
1
A
1
→
Γ
a
1
a
2
A
2
→
Γ
. . .
→
Γ
a
1
. . . a
k−1
A
k−1
→
Γ
a
1
. . . a
k
= w.
Γ
S → a
1
A
1
A
1
→ a
2
A
2
. . .
A
k−2
→ a
k−1
A
k−1
A
k−1
→ a
k
.
A
0
S A
k
S
a
1
−→ A
1
a
2
−→ A
2
a
3
−→ . . . A
k−2
a
k−1
−→ A
k−1
a
k
−→ A
k
,
w ∈ T (A
0
)
w w ∈ L(Γ) ⇔ w ∈ T (A
0
) L(Γ) = T (A
0
) ¤
α
∗
→
Γ
β
α β
Γ = (V, T, P, S)
α
∗
→
Γ
β, Γ
α
→
Γ
. . .
→
Γ
β,
(|β| + 1) · |V ∪ T |
|β|
|X|
X
Γ
α = α
0
→
Γ
α
1
→
Γ
. . .
→
Γ
α
n
= β.
Γ
|α
0
| ≤ |α
1
| ≤ . . . ≤ |α
n
|.
|α
0
| |α
0
| + 1
|α
0
| + 2
m m
V ∪T |V ∪ T |
m
m |V ∪ T |
m
α
i
= α
j
i < j
α
i
α
j−1
m
|V ∪ T |
m
|V ∪ T |
|α
0
|
+ |V ∪ T |
|α
0
|+1
+ . . . |V ∪ T |
|α
n
|
|V ∪ T |
|α
n
|
(|α
n
| + 1) · |V ∪ T |
|α
n
|
|α
n
| = |β|
¤
α
∗
→
Γ
β
A
0
, A
1
, . . . A
0
α
A
1
A
2
A
(|β|+1)·|V ∪T |
|β|
A
i+1
A
i
A
i+1
A
i
A
i
P
α
∗
→
Γ
β β ∈ A
(|β|+1)·|V ∪T |
|β|
Γ A = {0, 1}
L(Γ) = ∅
L(Γ) = {a}
L(Γ) = {Λ}
L(Γ) = A
+
L
(Γ) =
A
∗
L(Γ) = {1 . . . 1
| {z }
2n
6= Λ | n ∈ N, n 6= 0}
L(Γ) = {1 . . . 1
| {z }
2n
| n ∈ N}
L(Γ) = {1 . . . 1
| {z }
2n+1
| n ∈ N}
L(Γ) = {w 6= Λ | w }
L(Γ) = {a
n
b
n
| n ∈ N}
L(Γ) {w
1
, . . . , w
k
}
L(Γ)
a b + − ×
((a + b) + c) (a × b) + (a × c)
L(Γ) w
L(Γ)
R
0
R
1
0, 1, . . .
0 0, n n
n
n
n
P k > 0
k A
P
k
A
P
k
(x
1
, . . . , x
k
)
x
1
, . . . , x
k
1, . . . , k
A
P
k
(x
1
, . . . , x
k
)
f g f (¯x) ' g(¯x)
¯x
f(¯x) g(¯x)
k f : N
k
→
N P
A
P
k
(x
1
, . . . , x
k
) ' f(x
1
, . . . , x
k
)
x
1
, . . . , x
k
∈ N A
P
k
f
0 :
1 :
2 :
3 :
P
P
∗
P
∗
m
P
P
m + 1
P Q
P
0
P
∗
P
0
P
0
P
∗
P
n
P n P
P
m
P
∗
¤
P
P
0
0 :
1 :
∗
P
0 :
1 :
2 :
3 :
4 :
• I
• → i 6= k 6= j
i j k
i
i 6= j
→ i 6= j
0 :
1 :
¾
2 :
3 :
¾
4 :
5 :
6 :
7 :
8 :
¾
9 :
10 :
¾
i = j
• F k P
P
1
k
→
0 m
,
F
R
i
1
, . . . , R
i
k
j
s
u
0
, . . . , u
m
m
m i
1
, . . . , i
k
, s
P