, .
1.9. :
, (1.1)
VN - ( );
VT - ( , ..), VT Ç VN = Æ;
- , (VT È VN) + ´(VT È VN) *; (a, b) a b (: a b);
S - , S N.
. .
0. 0 ( ), , , .
1. - (-), a b, a Î (VT È VN)+, b Î (VT È VN)* | a | £ | b |. e -, .. e, Î VN.
2. - (-), : 
, 
3. 
(-), , , 
.
(-), , 
, .
e- Se, S .
1.15. L (G) k, k, k .
1.7. L= {0 n 1 n | n >0} - ( 1) G 1 ( 1.4) - ( 2) G 2= ({0, 1}, { S }, P 2, S),
P 2 S 0 S 1|01.
( 3), , L 2 -.
1.1.
; - ;
- ;
0 0.
1.1
1.8. . , , S.
) 0 L (G)= 
:
|
|
|
- 1) S aaCFD;
- 2) AD D;
- 3) F AFB | AB;
- 4) Cb bC;
- 5) AB bBA;
- 6) CB C;
- 7) Ab bA;
- 8) bCD e.
) - L (G)={ anbncn | n ³1} :
- 1) S aSBC | aBC;
- 2) CB BC;
- 3) aB ab;
- 4) bB bb;
- 5) bC bc;
- 6) cC cc.
) - L (G)={(a) n (cb) n | n >0} :
- 1) S aQb | accb;
- 2) Q cSc.
) L (G)={ w ^ | w Î{ a, b }+, } :
- 1) S A ^ | B ^;
- 2) A a | Ba;
- 3) B b | Bb | Ab.
1.16. G 1 G 2 , , .. 
.
1.17. G 1 G 2 , , .. 
.
1.9. G 1 G 2 = ({0, 1}, { S }, P 3, S), P 2: S 0 S 1|01, .. L (G 1)= L (G 2)={0 n 1 n | n >0} ( 1.7).
G 1 G 3 = ({0, 1}, { S }, P 3, S), P 3 S 0 S 1| e, .. L (G 3)={0 n 1 n | n ³0}.
