, . .
1. . . , . , , (), , (), . , . 5, 4. , , .
1.1. . , Ⳮ . .
D E .
, , () α→β, α,β - D U E. α→β, γ δ, γ = ωαh δ= ωβh, ω h - D U E. γ δ. . d0 ( d0 , - ) , E ( , d0 ). , d0.
:
D = {d0,d1}, E = {0,1} :
d 0 → 0d1
d1 → 1d1
d1 → ε
0 1 - , d0 d1 , d 0 . G1.
' :
d 0 ( ), 0d1 ( d0→0d1), 0 ( d1 → ε);
|
|
d 0 ( ), 0d1 ( d0→0d1), 01d1 ( d1 → 1d1), 01 ( d1 → ε);
d 0 ( ), 0d1 ( d0→0d1), 01d1 ( d0→0d1), 011d1 ( d1 → 1d1), 011 ( d1 → ε).
, 0, 01, 011 , () G1. , , , {0, 01, 011, 0111,...}.
{ε, 00,0000, 000000,...}.
d0 :
d 0 → 00d0
d0 → ε
0 - , d0 , d 0 - . G2.
' :
d0 ( ), ε ( d0→ ε);
d0 ( ), 00d0 ( d0→00d0), 00 ( d0→ ε);
d0 ( ), 00d0 ( d0→00d0), 0000d0 ( d0→00d0), 0000 ( d0→ ε);
d0 ( ), 00d0 ( d0→00d0), 0000d0 ( d0→00d0), 000000d0 ( d0→00d0), 000000 ( d0→ ε).
, ε, 00, 0000, 000000 , (䭭୭) G2. , , {ε, 00, 0000, 000000,...}.
1.2. , ', ( ) ( ).
, , .
, , . , :
0 d1
d0 1
d0 d1 , 0 1 , d0 d1 0 , d1 d1 1 .
, ( ), d0 , d1 , :
0 d0 d1, ;
|
|
01 - d0 d1, d1 d1, ;
011 - d0 d1, d1 d1, d1 d1, .
, {0, 01, 011, 0111,...}, G1. , , {0, 01, 011, 0111,...}. , {0, 01, 011, 0111,...}, G1.
, ( ) , , ( ) . d1 , , , 01 , , , d1 0. , , d1 . , d0 010, 010 , d1 01, , .
, , , :
1) , ( );
2) , ( ).
{ε, 00, 0000, 000000,...}, G2. :
d0 d1
d0 d1 , 0 , d0 d1 0 , d1 d0 1 . d0 .
:
ε d0, d0, , , , ;
00 - d0, d1, d1 d0, ;
0000 - d0, d1, d1 d0, d0 d1, d1 d0, .
, {ε, 00, 0000, 000000,...}, G2. , , {ε, 00, 0000, 000000,...}. , {ε, 00, 0000, 000000,...}, G2.
1.3. . , . .
|
|
2. . .
. :
1) Æ ;
2) {e} - ;
3) {ei}, ei Î , - ;
4) R S , R Ç S, RS, R* - ;
5) - , 1) 4) .
, 쳺, ⭭ ' , . , , , , e, , - , ', . , .
.
) Æ
) {e}; ') {0}; ) {1};
) {0,1} {0}È{1};
) {00, 01, 10, 11} - {0}{0}È{0}{1}È{1}{0}È{1}{1};
) {e, 01, 0101, 010101,} - ;
) - {e, 0, 00, 000, } - ;
) {e, 000111, 000111000111, 000111000111000111,} - ;
) {e, 0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 011, 101, 110, 111,} - .
, , 0,1 . , .
1. {e, 01, 0011, 000111,...}.
. , 0 1, . ij, , , - 0 1, . - 0, 1. , 0 1 .
:
{011, 00111, 000011111,...};
{010, 001100, 000111000,...} .
, , , .
, T, R, S 쳺 . , , . .
:
1) Æ , Æ;
2) e - , {e};
3) ei - , {ei}, ei Î ;
4) r s - , R S, (r + s), (rs), (r)* - , R È S, RS, R*;
5) t , 1) - 4) .
|
|
2. :
(01) {01};
(010) {010};
(0+1)* {0,1}*;
(e1 + e2) (e1 + e2 + e3 + e4) e1, e2, e3, e4, e1 e2.
, . : ; ; '. , , . . .
, - , . ', , - .
. e1 e2, R = {e1} È {e2}. , , (e1 + e2). (e2 + e1) . e1 e2, ({e1} È {e2})*. (e1 + e2)* (e2 + e1)*. , , .
. .
. r s ( r = s), .
, .
5. r, s, t , :
r + s = s + r;
r +(s + t) = (r + s) + t, r(st) = (rs)t;
r (s + t) = rs + st, (s + t)r = sr + tr;
re = e r= r;
r* = r + r*;
r + r = r;
(r*)* = r*;
Æ*= e;
Ær = rÆ = Æ;
r + Æ = r.
. r R, s - S. , , .
. .
3. . . ϳ , , .