. , , -, -, . , -, , -, , -.
. G({0,1,2,3,4,5,6,7,8,9,,+},{S,T,F},P,S):
P:
S T | +T | T
F | TF
F 0 | l | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
G - ( 2). , 0, 1, 2, 3 :
TF | TF TTF, 3, , , . ( ) G({0,1,2,3,4,5,6,7,8,9,,+},{S,},,S):
P:
S T | +T | T
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1T | 2T | 3 | 4T | 5T | 6T | 7T | 8T | 9T
G ( 3).
( 3) G({0,1,2,3,4,5,6,7,8,9,,+},{S,T},P,S):
;
+ | |
S 0 | 1 | 2 | | 4 | 5 | | 7 | 8 | 9 | S0 | Sl | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9
, , G, G G, ( 3).
G2({0,1},{A,S},P,S) :
S 01
0 001
0. , : L(G2) = {0n1n| n > 0}.
- G2'({0,1},{A,S},P,S) В:
S 01 | 01
0 001 | 001
- G2"({0,1},{S},P,S) Д:
S 0S1 | 01
, L = {0n1n| n > 0} - ( 2).
G3({,b,},{,,D,S},,S) :
S BD
b | b
b b
CD Dc
bDc bcc
abD abc
1. , . , : L(G3)={nbncn| n > 0}. , -, 2 3.
|
|
L = { nbncn| n > 0} - ( 1).
.
.
. , .
β = 12 α = 12 G(VT,VN,P,S), V = VTVN, 1,,2V*, V+, G : . β α : αβ. , β α , α, β.
1 2( ) . α β, G : αβ .
β α ( α*β) , :
β α (αβ);
γ, , : γ α β γ (α*γ γβ).
. , β α, αβ α β : αγ1γiγnβ, n1. γi γi-1.
. . , , . β α: αβ, .
α β ( ), α+β (, β α). , . , α4β , β α 4 .
G ({0,l,2,3,4,5,6,7,8,9,,+},{S,T,F},P,S):
:
S T | +T | T
F | TF
|
|
F 0|l|2|3|4|5|6|7|8|9
:
1. S TF TFF FFF 4FF 47F 479
2. S TF 8 F8 18
3. TF T0 TF0 T50 F50 350
4. TFT TFFT TFFF FFFF 1FFF 1FF4 10F4 1004
5. F 5
:
1. S * 479 S + 479 S 7 479
2. S * 18 S + 18 S 5 18
3. * 350 + 350 6 350
4. TFT * 1004 TFT + 1004 TFT 7 1004
5. F * 5 F 15 ( F + 5 !)
G. (, , ) .