- -
G = (N, T, P, S) - - . .
, , . S *u , u - . . () l ( r).
(V, E), V , E - , ((v, v1), (v, v2),..., (v, vn)). , v n , , v1, - , v2, ..
(V, E), f: V F ( ) F.
D ( ) w - G = (N, T, P, S), :
- D S;
- a T, e;
- A N;
- X - , X1,..., Xn - , X X1...Xk - P;
- , , w.
G , w, G.
G , A , A +A .
(-) - M = (Q, T, , D, q0, Z0, F),
- Q - , ;
- T - ;
- - ;
- D - Q(T {e}) Q *, ;
- q0 Q - ;
- Z0 - , ( );
- F Q - .
- (q, w, u),
- q Q - ;
- w T* - ; w ; w = e, , ;
- u * - ; u ; u = e, .
- M , .
D(q, a, Z) (p, v), q, p Q, a T {e}, w T*, Z u, v *.
|
|
- M (q0, w, Z0), w T*, .. , , , Z0.
- (q, e, u), q F, u *, .. , .
- , k 0 ( +, * k ).
, w - M, (q0, w, Z0) *(q, e, u) q F u *.
, (, ) M ( L(M)) - , M.
4.1. -
D :
D(q0, a, Z) = {(q0, aZ)},
D(q0, b, Z) = {(q0, bZ)},
D(q0, a, a) = {(q0, aa), {q1, e)},
D(q0, a, b) = {(q0, ab)},
D(q0, b, a) = {(q0, ba)},
D(q0, b, b) = {(q0, bb), (q1, e)},
D(q1, a, a) = {(q1, e)},
D(q1, b, b) = {(q1, e)},
D(q1, e, Z) = {(q2, e)}.
, L(M) = {wwR|w {a, b}+}, wR () w.
: w - M, (q0, w, Z0) *(q, e, e) q Q. , . ,
4.1. , ( ) .
. L = L(M) - M = (Q, T, , D, q0, Z0, F). - M', .
M' = (Q {q0', qe}, T, {Z0'}, D', q0', Z0', ), D' :
- (r, u) D(q, a, Z), (r, u) D'(q, a, Z) q Q, a T {e} Z ;
- D'(q0', e, Z0') = {(q0, Z0Z0')};
- q F Z {Z0'} D'(q, e, Z) (qe, e);
- D'(qe, e, Z) = {(qe, e)} Z {Z0'}.
(q0, w, Z0Z0') D' .2, (q, e, Y 1...Y kZ0'), q F .1, (qe, e, Y 1...Y kZ0'), q F .3, (qe, e, e) .4. , (q0, w, Z0) +(q, e, u) ( q F) M , (q0', w, Z0') +(qe, e, e) M'. L(M) = L', L' - , M' .
, M = (Q, T, , D, q0, Z0, ) - -, L. M', .
M' = (Q {q0', qf}, T, {Z0}, D', q0', Z0', {qf}), D' :
- D'(q0', e, Z0') = {(q0, Z0Z0')} - M;
- q Q, a T {e}, Z D'(q, a, Z) = D(q, a, Z) - M;
- q Q, (qf, e) D'(q, e, Z0') - .
, L = L(M'). __
|
|
- - -.
4.2. - , .
. G = (N, T, P, S) - -. - M, L(G) .
M = ({q}, T, N T, D, q, S, ), D :
- A u P, (q, u) D(q, e, A);
- D(q, a, a) = {(q, e)} a T.
, - G. , w T* S +w G , (q, w, S) +(q, e, e) M.
, M = (Q, T, , D, q0, Z0, ) - -, L. G, L.
G = ({ [qZr] | q, r Q, Z } {S}, T, P, S), P :
- (r, X1...Xk) D(q, a, Z), k 1,
s1, s2,..., sk Q;
- (r, e) D(q, a, Z), [qZr] a P, a T {e};
- S [q0Z0q] P q Q.
, M w w G.
G M , (q, w, A) +(p, e, e) , [qAp] +w.
, w L(G), S [q0Z0q] +w q Q. , (q0, w, Z0) +(q, e, e) w L. , w L, (q0, w, Z0) +(q, e, e). , S [q0Z0q] +w, w L(G). __
- M = (Q, T, , D, q0, Z0, F) (-), :
- D(q, a, Z) q Q, a T {e}, Z ;
- D(q, e, Z) , D(q, a, Z) = a T.
, -, -.
- , D(q, a, Z) = (p, u) D(q, a, Z) = {(p, u)}.
4.2. -
:
D(q0, X, Y) = (q0, XY), X {a, b}, Y {Z, a, b},
D(q0, c, Y) = (q1, Y), Y {a, b},
D(q1, X, X) = (q1, e), X {a, b},
D(q1, e, Z) = (q2, e).
, - L = {wcwR|w {a, b}+}.
, - , -. , , -, - (, , 4.1).
-.
M = (Q, T, , D, q0, Z0, F), , -, D, Q(T {e}) * Q *. (, , ) - , .
4.3. M = (Q, T, , D, q0, Z0, F) - -. - M', L(M') = L(M).
- M = (Q, T, , D, q0, Z0, F) , :
- D(q, a, u) q Q, a T {e}, Z *;
- D(q, a, u) , D(q, a, v) u v, x , u = vx v = ux;
- D(q, a, u) , D(q, e, v) , x , u = vx v = ux.
4.4. M = (Q, T, , D, q0, Z0, F) - -. - M', L(M') = L(M).
|
|
- - , , LL LR-.