x (VT U VN) G = (VT, VN, P, S),
:
1. V0 = {S}; i = 1
2. Vi = {x|x (VT U VN), A -> axb A Vi-1, a, b (VT U VN)* U Vi-1
3. Vi!= Vi-1, i = i + 1 2, VN = Vi VN; VT = Vi VT; P P, Vi; G = (VT, VN, P, S).
VN G = (VT, VN, P, S), {a VT* | A -> a}
:
N0, N1,
1. N0 = 0, i = 1
2. Ni = {A| (A -> a) P (Ni-1 U VT)*} U Ni-1
3. Ni!= Ni-1, i = i + 1 2, VN = Ni, P P, VN U VT; G = (VT, VN, P, S)
, .
()
: M(Q, V, P, R, F), :
Q
V
P , VxQ Q: U(Q), P(a, q) = U, a V, q Q, U Q
R Q, R Q
F F Q
, : V q Q: P(a, q) = {r}, r Q, P(a, q) = .
() .
: , A , t: F(A, t) = B.
(K, VT, F, H, S), K , VT - . , F , H . K, S - , - K.
= (K, VT, F, H, S) ; M = (K, VT, F, H, S) , , .
1. ʒ . ʒ [A1A2An], Ai
2. F F([A1An], t) = [B1Bm], 1 <= j <= m F(Ai, t) = Bj - 1 <= i <= n
3. H = {H1, H2, Hk}, a H' = [H1, H2, , Hk]
4. S = {S1, S2, , Sp}, S K, [Si], Si S - 1 <= i <= p.