.
- . 1
2- R, .
. 1 18 i,
18 ,
, - 18
{1, 2, 3, 4, 5, 6, 7} . 2.
1
ci | C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | C10 | C11 | C12 | C13 | C14 | C15 | C16 | C17 | C18 |
si | ||||||||||||||||||
xi | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X |
2
X1 | X5 | X2 | X4 | X6 | X6 | X4 | X3 | X3 | X0 | X7 | X0 | X3 | X7 | X4 | X5 |
- | |||||||||||||||
X0 | X4 | X5 | X7 | X2 | X5 | X1 | X2 | X2 | X0 | X6 | X1 | X1 | X3 | X7 | X5 |
G=(Vt, Vn, S, R), Vt={c1, c2, c3,..., c8} - ; Vn= {S,A,B,C,D,E,F } - ; S, Vn - ; R - , :
S→c1 c2 c3 A; S→c1 c4 c5 B; S→c6 C; S→c7 F; A→c8 D; A→c9;
B→c8 E; B→c9; C→c8 E; C→c9; D→c10 S; D→c11; E→c10 S;
E→c11; F→c12 c13 c14 c15; F→c16 c13 c14 c15; F→c17 c18 c15;
, ,
G=(Vt,Vn, S, R), Vt={x0, x1,2,..., 7} - ;
R' - ,
Vt Vt . 1.
S→x4 x0 x1A | x4 x7 x7B | x4C | x5F; A→x4D | x6; B→x4E | x6; C→x4E | x6;
D→x0S | x4; E→x0S | x4; F→x6 x0 x5 x2 | x0 x0 x5 x2 | x1 x2 x2
| - (), .
.
, G=(Vt, Vn, S, R). R :
S→x4 S1; S1→x0 S2; S2→x1 A; S→x4 S3; S3→x7 S4; S4→x7 B; S→x4 C; S→x5 F;
A→x4 D; A→x6; B→x4 E; B→x6; C→x4 E; C→x6; D→x0 S; D→x4;
E→x0 S; E→x4; F→x6 F1; F1→x0 F2; F2→x5 F3; F3→x2; F→x0 F4; F4→x0 F5;
F5→x5 F6; F6→x2; F→x1 F7; F7→x2 F8; F8→x2
|
|
,
Vn = {S1, S2, S3, S4, , , , D, E, F, F1, F2, F3, F4, F5, F6, F7, F8}
| Vn | 19.
.
A=(Q, , δ, q0, qk), Q - ; - ; δ - δ:x*Q→P(Q); P(Q) - Q; q0, Q - ; qk, Q - , qk≠q0.
. Vn Q, S - q0, qk, , L(G). , | Q | Q | Q | = | Vn | +1=20.
, 1 3 3, , 2 4.
3
S | S1 | S2 | S3 | S4 | A | B | C | D | E |
q0 | q1 | q2 | q3 | q4 | q5 | q6 | q7 | q8 | q9 |
F | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | - |
q10 | q11 | q12 | q13 | q14 | q15 | q16 | q17 | q18 | q19 |
q19.
, (. 4) (. 1).
(4) .
1
4
q | x0 | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
q0 | q1,q3,q7 | q10 | ||||||
q1 | q2 | |||||||
q2 | q5 | |||||||
q3 | q4 | |||||||
q4 | q6 | |||||||
q5 | q8 | q19 | ||||||
q6 | q9 | q19 | ||||||
q7 | q9 | q19 | ||||||
q8 | q0 | q19 | ||||||
q9 | q0 | q19 | ||||||
q10 | q14 | q17 | q11 | |||||
q11 | q12 | |||||||
q12 | q13 | |||||||
q13 | q19 | |||||||
q14 | q15 | |||||||
q15 | q16 | |||||||
q16 | q19 | |||||||
q17 | q18 | |||||||
q18 | q19 | |||||||
q19 |
.
|
|
,
qi ,
Xj.
. .1
,
. 5,
- . 2. 5
q | x0 | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
q0 | q1,3,7 | q10 | ||||||
q1,3,7 | q2 | q9 | q19 | q4 | ||||
q2 | q5 | |||||||
q4 | q6 | |||||||
q5 | q8 | q19 | ||||||
q6 | q9 | q19 | ||||||
q8 | q0 | q19 | ||||||
q9 | q0 | q19 | ||||||
q10 | q14 | q17 | q11 | |||||
q11 | q12 | |||||||
q12 | q13 | |||||||
q13 | q19 | |||||||
q14 | q15 | |||||||
q15 | q16 | |||||||
q16 | q19 | |||||||
q17 | q18 | |||||||
q18 | q19 | |||||||
q19 |
2
.
( ) , , . , ( - ) . (.6), (qi, qj), i≠j . . qi qj k, qi , qj - , qj qj , . , - .5 , , . 6 qi, qj (qv, qw), qi qj .
6
1,3,7 | X | ||||||||||||||||||||
X | X | ||||||||||||||||||||
X | X | X | |||||||||||||||||||
X | X | X | X | ||||||||||||||||||
X | X | X | X | ||||||||||||||||||
X | X | X | X | X | X | ||||||||||||||||
X | X | X | X | X | X | ||||||||||||||||
X | X | X | X | X | X | X | X | ||||||||||||||
X | X | X | X | X | X | X | X | X | |||||||||||||
X | X | X | X | X | X | X | X | X | X | ||||||||||||
X | X | X | X | X | X | X | X | X | X | X |
|
|
. 6
. ,
. 4
: {q5, q6}, {q8, q9,}, {q12, q15},{q13, q16, q18}.
, ,
.
9
: q0, q1,3,7, q2, q4, q10, q11, q14, q17, q19,
r :
r0={q5, q6}, r1={q8, q9}, r2={q12, q15}, r3={q13, q16, q18}, r4 = {q1,3,7},
r5={q2}, r6={q4}, r7={q10}, r8={q11}, r9={q14}, r10={q17}, r11={q19}, r12={q0}.
, , 13 , . . 3, - . 7
3
7
r | x0 | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
r0 | r1 | r11 | ||||||
r1 | r12 | r11 | ||||||
r2 | r3 | |||||||
r3 | r11 | |||||||
r4 | r5 | r1 | r11 | r6 | ||||
r5 | r0 | |||||||
r6 | r0 | |||||||
r7 | r9 | r10 | r8 | |||||
r8 | r2 | |||||||
r9 | r2 | |||||||
r10 | r3 | |||||||
r11 | ||||||||
r12 | r4 | r7 |