A i B i , , i X ii X = AX∪B. iX = .
. ii, X⊂ B. , ω = e. ω∈X, ω∈AX∪B. i , i ω∈Bi, , ω∈ B. i, , i i ω n , ω∈X, ω∈ B, i α n. α∈X = AX∪B, , α∈B⊂ B
α = βγ β∈Aiγ∈X. β ei, ,
|γ| < |α|. , i , γ∈ Biα∈A B⊂ B. i i, , X⊂ B.
, ii, , ⊂X i n ≥ 0. n = 0, , B = B⊂AX∪B = X. n> 0 B = A( B) ⊂AX. ,
B⊂AX⊂AX∪B = X. .
.
X i i. () ii X :
1) ∅ ;
2) a ∈ X {a} ;
3) A i B , A ∪ B, AB ;
4) i i.
p.
1) {e} , {e} = ;
2) {001, 110} i i,
{001, 110} = ({0}{0}{1}) ∪ ({1}{1}{0});
, i X :
1) ∅ , ;
2) e , {e};
3) a ∈ X a , {a};
4) i , A i B ii, ()+(), ()() i , A ∪ B, AB i ii;
5) i i i X i.
ii , , i i ii ∗, i i i i +. , 01 {01}, , , 001
i i, i i i i i 001.
i i i, . , 1+∅ i 1 {1}. ,
ii (=), i
.
3.2. p. α, β i γ i . i:
α + β = β + α; = e; α + (β + γ) = (α + β) + γ; α(βγ) = (αβ)γ; α(β + γ) = αβ + αγ;
|
|
(α + β)γ = αγ + βγ; αe = eα = α; ∅α = α∅ = ∅; = α + ; = ; α + α = α;
α + ∅ = α.
. α i β A i B ii. i α+β A∪B, β +α B ∪A. A∪B = B ∪A ᒺ, α + β = β + α. i i. .
i : = .
i i i , i i X ∪ {e}. i r, , , :
i ii , i i i , i i, r:
i, i , i i i i +, :
1)i i f +g i i i f i g:
2) i i fg i i i f i g:
3) i i i i e, f i e:
r G(r) i i , . , i G(r) X ∪ {e}. G(r) ii , i i , i i . x i L(r) i i i i, i G(r) i , ii x.
- i G(r), i i i i i .
3. . .
. .
G = (N, T, S, P), N i , i , T , i , S ∈ N i , P i i ( ) ξ → η, ξ η ii
N ∪ T. i i , i i . ii N ∪T, , . , i i ii A .
G = (N, T, S, P) , i = σ ξ τ ( i i σ, ξ i τ), = σ η τ ii N ∪ T. ξ → η i G, , , i ⇒ . , ,..., ii N ∪ T i, ⇒ ⇒ ⇒... ⇒ ⇒ , , i .
, G = (N, T, S, P), i i ii, i S. L(G). , L(G) = {ω ∈ T∗| S ⇒∗ω}.
|
|
A → ,A → ,...A → , ᒺ A → | |... | .
i i. ii, i ii .i. i ii , i . i i .
i 0 i. 1 i i ξ → η, η , i ξ, i ξ → e. i 2 i A → ω, A i , ω ∈ . 3 i i:
A → ωB, A → ω i A → e, A, B i, ω ii. I , n, n = 1, 2, 3, n−1. 2 i, i A ii i
A → η i η i i , i, i .
, 2, i. i i P i γ δ → γ ν δ, || ≤ |η|, 1, , i i ν i i γ... δ, ii i. , 1, . 3 ii.
iii i i:
A → ωB, A → ω i A → e, A, B i, ω ii. iiii i iii . i i i .
ω i L(G) i G i i i, i S ω G. i , ω i S.
, . , i G = ({S}, {a, b, c}, S, P), P = {S →SbS | ScS | a} i abaca ∈ L(G).
S ⇒ SbS ⇒ SbScS ⇒ abScS ⇒ abSca ⇒ abaca (),
S ⇒ ScS ⇒ SbScS ⇒ abScS ⇒ abSca ⇒ abaca ().
i G =(N, T, S, P) :
1) i S.
2) i , i e i : A ∈ N i A → ... G, ∈ N ∪ T i i A ∈ N :
i i ω ∈ , , ω.
ω ii ω i G. , ii i i ω. i G = (N, T, S, P) -, i ω ∈ L(G), ii . G S → if b then S else S | if b then S | a.
, i
if b then if b then a else a
if b then (if b then a) else a
|
|
if b then (if b then a else a),
ii i .
4. ̳ . . .
i, n i i m i. , ii i , ,..., . I − . i i i i. i i (i) i , ,..., .i i i i , ii i i . i i i i. - ii i , ,i i i, i , i ii.
i ii, i i i. i i , i: i X = { ,..., }, i
Y = { ,..., } ii i Q = { ,..., }.
i, i . i i (i ). i i ii i.
i, i ii . i i i, i i i . i i i Q.
i A = (Q,X, Y, δ, f, , F) ii, i i Q, i i X, i i Y, i i δ: Q×X → Q, i i f: Q×X → Y, i i F. X i Y ii i i i i . δ(a, x) = , , Q i i i x ∈ X , x Q i a .
, f(a, x) = y, , Q i a i x ∈ X i y ∈ Y.
A = (Q,X, Y, δ, f, , F) i, i Q, X i Y ii, i i, i.
i , i i i i i i, i , .
I , δ i, i, i . i. i δ i, i. , i Q a b, i i ω ∈ F(X). i i i , i. , i i i i i.
i i i i i i, i i ii ii . i i i i,
(Q, X Y) .
i i i. i .
i - i (X, Y, f), f: X → Y.
i i i X i i Y, i x ∈ X i i i y ∈ Y.
|
|
i (Q, Y, δ, f) δ: Q → Q, f: Q → Y. i.
i, X- a i (Q,X, δ, , F), F i i , i , ∈ Q .
i ii. A = (Q,X, Y, δ, f) , i f(a, x) i i δ(a, x) i f(a, x) = h(δ(a, x)), h: Q → Y. i i t , y(t) = g(q(t)). i h i ii , h(a) i a ii .
i i , i i i i i i i i i.
i i i i - i i ii, iii i i, i i . i i ( ) i i- , ii
ii a ∈ Q i j- , ii x ∈ X, δ(a, x) = b. i i ( ) i i- i j- f(a, x) = y ∈ Y. ,
ii i i, i i i.
i i i i A A. i i i , ii . i iii i: i i, - i i. i iii i i i i i i δ i f , δ(a, x) = i f(a, x) = y, i i, ii (x/y),i , i i i i i i
(), ii (x/y), i δ i f ii δ(a, x) = i f(a, x) = y. i , i , i , i , . i .
5. . .
i δ i, i. , i Q a b, i i ω ∈ F(X).
ii i i i () .
p. A = (Q,X, δ, q0, F) i , i A, Q = {q0, q1, q2, q3}, X = {0, 1}, F ={q1, q2}, i i δ :
i A :
L(A), i A.
, ω ∈ L(A), A i ω i i F. , q3 ii ω, i
i i ω ∉ L(A). , i q2, i , i i i . , L(A) i 0 (i i q1) i i , i i 00. , L(A) 0 + 00(0 + 1 .
2.2. p. , i A = (Q,X, δ, q0, F), i :
i i 3.2, ii ω q6, i A i, , i q3, i ω. , i i i q0 q3. i q0 q3:
(q0, q1, q2,..., q2, q3); (q0, q1, q5,..., q5, q3); (q0, q4, q5,..., q5, q3).
ii , i 01 0, 00 1 i 10 1 ii. ,
p. , i i i ii X = {0, 1}, i i 01.
|
|
, 01(0 + 1 . :
, i i q i a (q, a) ∈ Q × X. , q3 i i q0 → q3 i q1 → q3 1 i 0 ii. :
p. , i i i ii X = {0, 1}, i i i 00.
ii, (0+1 00(0+1 00 i i. , 00 i i . i i.
, ii ω = x1x2... xn, xi∈{0, 1}. i i x1x2, x2x3,... xn−1xn i i , i 00, , w i . i .
1.
i q2, i , i 00. , x1x2 = 00, ω i.
2. x1 = 1, i x1x2 i i x2x3. , i q0, δ(q0, 1) = q0.
3. x1 = 0 i x2 = 1, i i x1x2, i x2x3 i 00. , i q0 i i x3x4. , δ(q1, 1) = q0. :
p. , i i i ii X = {0, 1}, i i i 00101.
i, i i, :
p. , i i i ii X = {0, 1}, i i 01. , :
q0 q1 , " i 01"" i 0 01"ii. i, i i,
δ(q0, 1) = q0 i δ(q1, 0) = q1. q2 i i i , i δ(q2, 0) = q1 i δ(q2, 1) = q0. , :
p. , i i i i , i i ᒺ, i, , ii i ii.
I ᒺ , i i. A1 = (Q1,X, δ1, q0, F1) iA2 = (Q2,X, δ2, q0, F2) (ii, Q1 i Q2 , i ii ). A = A1 × A2 i A1 i A2 .
A = (Q,X, δ, , F).
Q = Q1 × Q2 = {(qi, qj) | qi∈ Q1, qj∈ Q2},
δ((qi, qj), a) = (δ1(qi, a), δ2(qj, a)) i = (q0, q0).
6. . .
I , δ i, i, i . i.
i i () (Q,X, δ, , F) i , i i e-. , q i i a δ(q, a) i i (q, a) i i Q,
δ(q, a) = { , ,..., }. ii , i a i q i i , ,..., . , δ(q, a) = ∅ , ""i , i i
, i ii . i , . i i i i, e- (e-). e-i i ( i ), i i i i , ,..., . , i i :
δ: Q × (X ∪ {e}) → , i i i Q. i i :
i , , i ,
δ(q, a) = { , ,..., }, i k i q , ,..., i i i ii a.
, A1 (, F = { }):
i i ω i i . , i i ω , i i i i i i i.
, i ω, i i i i.
, i i ω, i e-. e- i P ⊂ Q i, i i q ∈ P e- ( q q). ,
i i δ × (X ∪ {e}),
i :
, (Q,X, δ, q0, F) i ω, δ({q0}, ω) ∩ F ∅. L(A) , i A,
p. , i i i i , i i ii.
ii ii iii ii , , i, ii i i i,i i i . , , i , i .
A = (Q,X, δ, q0, F). ω∈ i, i i i ω, = δ({q0}, ω), δ ii, i × . , Qe = cle({q0}).
, ω i ii i i, . , i i ⊂Q i
i i . I ,
:
, ω∈ , a∈X.
ii, iQi, , i. i, ⊂ i, , | | ≤ .
i, = , = ia∈X. i,ii . i i, i . i i.
p 1. i ii i, i .
1 , i L: L, i i .
p. i i i .