3
. .
:
;
.
. , . , .
L - T. , . () . , , , , , .
, , . , . . .
G = (N, T, P, S), (3.1)
N -
(),
T - ( N),
S - N, ,
- , : .
. pi = (a, b) () a Þ b. a b - , . :
a b;
a b.
, P : , , , . pi - (pi1, pi2), p i1 = - , , pi2 = , (e - ).
a pi1, , pi, b, pi1 pi2. , b a .
:
a,b,c,d 0,1,...,9;
A, B, C, D, S ( S - );
|
|
U, V,..., Z ;
a, b, g... ;
u, v, w, x, y, z - ;
( ) e;
. , A cd, A cd.
, , , . , , .
G1:
G1 = ({A, S}, {0, 1}, P, S), (3.2)
P:
1. S 0A1;
2. 0A 00A1;
3. A e.
G, , , G.
L (G), G, - , G.
ÞG , :
j ÞG y (3.3)
: y j G = (N, T, P, S) : abg b d , abg ÞG adg.
ÞG+ ( ). j ÞG+ y : y j .
ÞG* ( ). j ÞG* y : y j.
ÞK k- Þ. , a ÞK b, a0 a1 a2 a3... ak +1
a = a0, a1,... ai - 1 Þ ai, 1 ≤ i ≤ k ak = b (3.4)
G1:
S Þ 0A1 Þ 00A11 Þ 0011; (3.5)
S Þ1 0A1; S Þ2 00A11; S Þ3 0011; (3.6)
S Þ+ 0A1; S Þ+ 00A11; S Þ+ 0011; (3.7)
S Þ * S; S Þ * 0A1; S Þ * 00A11; S Þ * 0011, (3.8)
0011 Ì L (G1).
, , . , . . G :
, :
A xB A x, (3.9)
A, B - ,
x - , ;
- () , : A a, A Î N, a Î , , , ;
- () , P : a b, |a| £ |b|. , , , , , ( );
|
|
, .
:
G2 = ({S,}, {0,1}, P, S), (3.10)
P:
1. S 0S;
2. S 1S;
3. S e,
{0, 1}*.
-:
G3 = ({E, T, F}, {a, +, *, (,)}, P, E), (3.11)
P:
1. E T;
2. E E + T;
3. T F;
4. T T * F;
5. F (E);
6. F a.
.
-:
G4 = ({B, C, S}, {a, b, c}, P, S), (3.12)
P:
1. S aSBC;
2. S abc;
3. CB BC;
4. bB bb;
5. bC bc;
6. cC c,
{ a n b n c n }, n ≥ 1.
1. -.
2. - : e, e - . .. - -. .
. L G, L G.
: L(G3) - G3.
- -. - ( ). [14].