Морозов А.С. Введение в вычислимость
Подождите немного. Документ загружается.
½¼
¾»
"!
#Ã
"!
#Ã
' $
»
¼
?
¾
& %
6
¾
½
-
1
1
0
0
q
0
I
q
1
• A = {a
0
, . . . , a
n
}
• Q = {q
0
, . . . , q
m
}
• δ : Q ×A → Q
q a δ(q, a)
• q
0
∈ Q
• F ⊆ Q
(Q, A, δ, q
0
, F )
I
{0, 1}
0
q
0
q
1
1
q
0
s = s
0
s
1
. . . A
q
0
δ(q
0
, s
0
), δ(δ(q
0
, s
0
), s
1
), δ(δ(δ(q
0
, s
0
), s
1
), s
2
), . . .
F
s
s
δ δ
∗
Q ×A
∗
δ
∗
(q, w)
q w
δ
∗
(
q,
Λ) =
q,
δ
∗
(q, sa) = δ(δ
∗
(q, s), a),
s ∈ A
∗
a ∈ A
A = (Q, A, δ, q
0
, F )
s ∈ A
∗
δ
∗
(q
0
, s) ∈ F
A T (A)
T (A) = {s ∈ A
∗
| δ
∗
(q
0
, s) ∈ F }.
L = T (A) L
A L
A L = T (A)
s = s
0
s
1
. . . s
k
q
0
s
0
s
1
. . . s
k
s
δ(q, s)
q
s
∆(q, s)
q s
∆(q, s) ∅
A
(Q, A, ∆, q
0
, F )
∆ Q ×A
Q
s = s
0
s
1
. . . s
k
A = (Q, A, ∆, q
0
, F )
q
0
= r
0
, r
1
, . . . , r
k+1
r
1
∈ ∆(r
0
, s
0
)
r
2
∈ ∆(r
1
, s
1
)
. . .
r
k+1
∈ ∆(r
k
, s
k
)
r
k+1
∈ F
s
s
F
T (A)
A
s = s
0
s
1
. . . s
k
s
A
A T (A) = T (A)
A = (Q, A, ∆, q
0
, F )
A = (Q, A, ∆, q
0
, F )
• Q Q
• ∆(q, a) =
S
r∈q
∆(r, a) q ∈ Q a ∈ A
• q
0
= {q
0
}
• F =
©
q ∈ Q | q ∩ F 6= ∅
ª
T (A)
T (A) ⊆ T (A) T (A) ⊆ T (A)
T (A) ⊆ T (A)
s = s
0
s
1
. . . s
k
∈ T (A)
r
0
, r
1
, . . . , r
k
, r
k+1
A q
0
= r
0
r
1
∈ ∆(r
0
, s
0
)
r
2
∈ ∆(r
1
, s
1
)
. . .
r
k+1
∈ ∆(r
k
, s
k
)
r
k+1
∈ F
A s = s
0
s
1
. . . s
k
A
q
0
= r
0
, r
1
= ∆(r
0
, s
0
), . . . , r
k
= ∆(r
k−1
, s
k−1
), r
k+1
= ∆(r
k
, s
k
).
r
k+1
∈ F
s ∈ T (A) i = 0, . . . , k +
1 r
i
∈ r
i
i = k + 1
r
k+1
∈ r
k+1
r
k+1
∈ F r
k+1
∩F 6= ∅
F r
k+1
∈ F
i = 0
r
0
= q
0
∈ {q
0
} = q
0
= r
0
r
i
∈ r
i
r
i+1
∈ ∆(r
i
, s
i
) ⊆
[
q∈r
i
∆(q, s
i
) = ∆(r
i
, s
i
) = r
i+1
.
T (A) ⊆ T (A)
s ∈ T (A) A
A
q
0
= r
0
, r
1
= ∆(r
0
, s
0
), . . . , r
k
= ∆(r
k−1
, s
k−1
), r
k+1
= ∆(r
k
, s
k
) ∈ F .
r
k+1
∈ F F r
k+1
∈
F ∩r
k+1
r
k+1
∈ F r
k+1
∈ r
k+1
=
∆(r
k
, s
k
) =
S
r∈r
k
∆(r, s
k
) r
k
∈ r
k
r
k+1
∈ ∆(r
k
, s
k
)
r
k
r
k−1
r
0
, . . . , r
k
, r
k+1
r
i
∈ r
i
r
i+1
∈ ∆(r
i
, s
i
)
i = 0, . . . , k r
0
∈ r
0
= q
0
= {q
0
} r
0
= q
0
s ∈ T (A) ¤
A
L = ∅ A = {0}
L = {Λ} A = {0}
L = {0} A = {0, 1}
L = A
A = {0, 1, 2}
L = {0}
∗
A = {0, 1}
L = {0, 1}
∗
A = {0, 1, 2}
00 A =
{0, 1}
00
A = {0, 1}
01 A =
{0, 1, 2}
00 A =
{0, 1}
01 A =
{0, 1, 2}
1
0 A = {0, 1, 2}
1
A = {0, 1, 2}
L = {1 . . . 1
| {z }
2n
6= Λ | n ∈ N} A = {0, 1}
L = {s ∈ A | s 0
1 } A = {0, 1}
L = {f . . . f
| {z }
n
(0) | n ∈ N} A = {f, 0, (, )}
L = {s ∈ {a, b}
∗
| s b}
L = {s ∈ {a, b}
∗
| s b }
L = {s ∈ {a, b}
∗
| s abab}
L = {s ∈ {a, b}
∗
| s abab}
L = {s ∈ {a, b}
∗
| s a
b }
{0, . . . , 9}
0
+a
0
a
1
. . . a
n
−a
0
a
1
. . . a
n
a
0
6= 0 a
i
∈ {0, . . . , 9} {+, −, 0, . . . , 9}
∗
1 0 0
1 0 1 1
1 1 1 1
.
∗
∗ 1 0 0
1 0 1 1
1 1 1 1
.
∗
1
1
1
0
1
0
1
1
0
1
1
x
y
z
x, y, z ∈ {∗, 0, 1}
A = (Q, A, δ, q
0
, F )
q ∈ Q a ∈ A δ(q, a) 6= q
0
A ˜q
0
A = (Q, A, δ, q
0
, F ) A
0
= (Q
0
, A, δ
0
, ˜q
0
, F
0
)
T (A) = T (A
0
) A
0
A
˜q
0
q
0
˜q
0
q
0
q
0
6= q
0
˜q
0
q
0
q
0
q
00
q
0
q
0
q
00
˜q
0
q
0
q
0
˜q
0
˜q
0
˜q
0
q
0
q
0
A
∗
T (A
0
) ∪T (A
1
)
A
0
0
A
0
1
T (A
0
) = T (A
0
0
) T(A
1
) = T (A
0
1
)
½¼
¾»
q
0
½¼
¾»
q
00
½¼
¾»
q
0
½¼
¾»
q
00
½¼
¾»
½¼
¾»
½¼
¾»
. . . . . . . . . . . .
²¯
?
c
²¯
?
c
I
q
0
I
q
0
¯q
0
?
a
?
a
6
b
S
S
S
S
S
So
b
¶
¶
¶
¶
¶
¶/
a
-
c
=⇒
A
∗
A
∗
A
0
A
1
T (A
0
) ∪T(A
1
)
A
A F
A ∩ B = A ∪ B
A
0
A
1
µ´
¶³
I
'
&
$
%
'
&
$
%
A
0
A
1
µ´
¶³
I
'
&
$
%
A
0
µ´
¶³
I
'
&
$
%
A
1
⇓
A
1
A
0
A
1
A
1
A
0
α ∈ T (A
0
)
A
1
α
β ∈ T (A
1
)
T (A
0
)T (A
1
)
T (A
0
)T (A
1
)
A
A
∗
T (A)
∗
= T (A
∗
)
a q
a
q A
A