zn, n- .
AN={QN, ƩN, δN, q0N, FN}; AD={QD, ƩD, δD, q0D, FD}; L(AN)=L(AD)
1) ƩN ƩD
2) QD ⊆ 2QN, , - , QD.
3) F , , FN .
4) . . S ≤ QN a δs(a,s)=
A B C D | |||
→q0 q1 * q2 q0q1 * q0q2 * q1q2 * q0q1q2 | q0q1 ∅ q2 q0q1 q0q1q2 q2 q0q1q2 | q0 q2 q2 q0q2 q0q2 q2 q0q2 |
, , . {q0}. .
S . , . SU{S(δD(S,Q)=S, S ∈δ, a ∈ Ʃ}. : D={QD, ƩD, δD, {q0}, FD} N={QN, Ʃ, δN, q0, FN} , L(D)=L(N).
2: L , .
: 1) q0 . , { q0} . . . , q0 q1, q2,, qn, { q0, r1, , rk, p} . , , r1, , rk , q0 .
-.
E=(Q, Ʃ, δ, q0, F).
δ, Ʃ U [Ɛ]xQ→Q
: , :
Ɛ | 0..9 | . | +,- | |
→q1 q2 q3 q4 q5 | q2 ∅ q5 q5 ∅ | q0∅ q2,q3 ∅ q4 ∅ | ∅ q4 q4 ∅ ∅ | q2 ∅ ∅ ∅ ∅ |
- , Ɛ-. ECLOSE(q) q.
: δ^(w,q0), δ^(Ɛ,q)=Ɛ(q); : L(E)={w|δ^(w,q0) ⋂F=∅}; : L Ɛ- , .
.
1) L M, L ∪ M , L, M, . , L = {001, 10, 111} M={Ɛ, 001}, L ∪ M = {Ɛ, 10, 001, 111}.
2) L M . , L M. , L = {001, 10, 111} M={Ɛ, 001}, LM {001, 10, 111, 001001, 10001, 111001}
|
|
3) L L* . , L. L* , L0={Ɛ}, L1=L Li I > 1 LL..L ( i L).
.
Ɛ ∅ , { Ɛ } ∅, , .. L{Ɛ}={Ɛ} L{∅}={∅}.
a , , {}, .. L(a)={a}.
, , , L, .
E F ,
1) E + F , L(E) L(F), .. L(E + F)=L(E) ∪L(F).
2) EF , L(E) L(F). , L(EF)=L(E)L(F).
3) E* - , L(E), , L(E*)=(L(E))*.
4) (E) , L(E), E, .. L((E))=L(E)
:
1) *; 2) ; 3) (+)