.
.
( , )
1999
519.682.1+681.142.2
, , , . .
, : , , . .
, .
.. , , .. .
:
. ..
. ..
.., .. . . ( II ) -
( )
( 040777 23.07.96), 1998.-62 .
- . ..
ISBN 5-89407-032-5
Ó . .., 1999
.
, . , - , ( ). - , , - . . , , , ; , .
: - .
, "" .
: V .
: , , . e.
|
|
V :
(1) e - V;
(2) a - V a - , aa - V;
(3) b - V , (1) (2).
: a b - , ab ( ) a b.
, a = ab b = cd, ab = abcd.
a ae = ea = a.
: ( ) a , .
a aR.
, a = abcdef, aR = fedcba.
: e = eR.
: n- a ( an) n a.
a0 = e; an = aan-1 = an-1a.
: - .
, a = abcdefg, a 7.
a | a |. e 0.
: V - .
: V* , V, e.
, V={0,1}, V* = {e, 0, 1, 00, 11, 01, 10, 000, 001, 011,...}.
: V+ , V, e.
, V* = V+ È {e}.
, V V*.
[3]. . .
: A ´ B A B { (a,b) | a Î A, b Î B}.
: G - (VT, VN, P, S),
VT - (),
VN - (), -
VT,
P - (VT È VN)+ ´ (VT È VN)*; (a, b) P a b,
S - () , S Î VN.
a b1 a b2... a bn
a b1 | b2 |...| bn.
bi , i = 1, 2,...,n, a.
: G1 = ({0,1}, {A,S}, P, S), P
S 0A1
0A 00A1
A e
: b Î (VT È VN)* a Î (VT È VN)+ G = (VT, VN, P, S) ( a b), a = x1gx2, b = x1dx2, x1, x2, d Î (VT È VN)*, g Î (VT È VN)+
g d P.
, 00A11 0A1 G1.
: b Î (VT È VN)*
a Î (VT È VN)+ G = (VT, VN, P, S) ( a Þ b), g0, g1,..., gn (n>=0), , a = g0 g1 ... gn= b.
|
|
: g0, g1,..., gn n.
, S Þ 000A111 G1 (. ), .. S 0A1 00A11 000A111. 3.
: , G = (VT, VN, P, S), L(G) = {a Î VT* | S Þ a}.
, L(G) - VT, S P.
, L(G1) = {0n1n | n>0}.
: a Î (VT È VN)*, S Þ a, G = (VT, VN, P, S).
, , , .
: G1 G2 ,
L(G1) = L(G2).
,
G1 = ({0,1}, {A,S}, P1, S) G2 = ({0,1}, {S}, P2, S)
P1: S 0A1 P2: S 0S1 | 01
0A 00A1
A e
, .. L(G1) = L(G2) = {0n1n | n>0}.
: G1 G2 ,
L(G1) È {e} = L(G2) È {e}.
, , , , , e.
,
G1 = ({0,1}, {A,S}, P1, S) G2 = ({0,1}, {S}, P2, S)
P1: S 0A1 P2: S 0S1 | e
0A 00A1
A e
, .. L(G1)={0n1n | n>0}, L(G2)={0n1n | n>=0}, .. L(G2) L(G1) , L(G1) .
( )
0:
G = (VT, VN, P, S) 0, ( , ).
1:
G = (VT, VN, P, S) , P a b, a Î (VT È VN)+, b Î (VT È VN)+
| a | <= | b |.
G = (VT, VN, P, S) - (), P a b, a = x1Ax2; b = x1gx2; A Î VN;
g Î (VT È VN)+; x1,x2 Î (VT È VN)*.
1 -.
, , , , , , -.
2:
G = (VT, VN, P, S) - (), A b, A Î VN, b Î (VT È VN)+.
G = (VT, VN, P, S) - (), A b, A Î VN,
b Î (VT È VN)*.
2 - -.
, - -.
3:
G = (VT, VN, P, S) , A tB A t, A Î VN, B Î VN, t Î VT.
G = (VT, VN, P, S) , A Bt A t, A Î VN, B Î VN, t Î VT.
3 (, -) .
, , , , , , .
|
|
:
(1) -;
(2) -;
(3) - -;
(4) - ;
(5) - 0.
(6) 0.
: -, A e, - .
: L(G) k, k.
:
(1) -, -, (, L = {anbn | n>0}).
(2) - -, -, - (, L = {anbncn | n>0}).
(3) - 0.
: -, , -.
: , k, , k (k>k), . , k, k.
, - G1 = ({0,1}, {A,S}, P1, S)
- G2 = ({0,1}, {S}, P2, S),
P1: S 0A1 P2: S 0S1 | 01
0A 00A1
A e
L = L(G1) = L(G2) = { 0n1n | n>0}. L -, .. -, . , .. , [3].