: .
ᒺ , .
(<_, _>)
.
:
= < Q, S, d, q0, F>,
- Q = {q0, q1,.., qn-1} ;
- S = {a1, a2,.., am} ( );
- q0 Î Q ;
- d Q*S P (Q). ³ d ;
- F Í Q . F .
, (q, w) Î Q*S* . , . |=, :
(q1,aw) |= (q2,w), d(q1, a) q2 w Î S*.
. () w,
(q0, w) |=* (q, e) q Î F,
|=* - - |=.
. , ( )
L(M)={ w | w Î S* (q0, w) |=* (q, e), q Î F }
, , d, :
- d;
- .
d - (qi,aj), aj Î S, qi Î Q,
(qi,aj) = { qk |, qk Î d(qi,aj ) }
ij - G(V, P), V , P , qi qj ak , qjÎd(qi,ak ). :
ak
qi qj
, : qi.
1. , .
U, u
1,.., 9 L, l
1,.., 9 U, u L,l
q0 0,.., 7
L, l U, u
0 0,.., 7
U, u L, l
A,.., F,a,.., f, 0,.., 9
X, x
A,.. F, U, u L, l
a,.., f, L, l
0,.., 9 U, u
. 1.
, .
. , d(qi, ak) qi Î Q ak Î S.
|
|
: 1,
L(M) = L(M1).
: ,
=< Q, S, d, q0, F>
1=< Q1, S, d1, q01, F1> :
1. Q1 = P (Q), 1 Q.
2. q01= { q0 }, { q0 } Î P (Q).
3. F1 S Î P (Q), S Ç ¹ Æ.
4. d1(S, a) = {q | q Î d(qi, a), qi Î S }.
i, (S,w) |=i (S1,e), ,
S1= { q | (qi, w)) |=i (q, e), qi Î S },
, ({q0}, w) |=* (S1, e), S1 Î F1, ,
(q0, w) |=* (q, e), q Î F. , L(M) = L(M1).
: . 2n 1.