\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 LL(k)-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a.
\n\u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e G=(N,E,P,S) — \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u0430\u044f \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 \u0438 w=a1,a2…an — \u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u0438\u0437 L(G). \u0422\u043e\u0433\u0434\u0430 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u0430\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043b\u0435\u0432\u043e\u0432\u044b\u0432\u043e\u0434\u0438\u043c\u044b\u0445 \u0446\u0435\u043f\u043e\u0447\u0435\u043a b0,b1..bm, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0439 S=b0,bi,pi ? bi+1 \u043f\u0440\u0438 0<=i<m \u0438 am=w. \u041f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c p0p1..pm-1 -\u043b\u0435\u0432\u044b\u0439 \u0440\u0430\u0437\u0431\u043e\u0440 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 w.
\n\u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0447\u0442\u043e \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043d\u0430\u0439\u0442\u0438 \u044d\u0442\u043e\u0442 \u043b\u0435\u0432\u044b\u0439 \u0440\u0430\u0437\u0431\u043e\u0440, \u043f\u0440\u043e\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044f w \u043e\u0434\u0438\u043d \u0440\u0430\u0437 \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e. \u041c\u043e\u0436\u043d\u043e \u043f\u043e\u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e, \u0441\u0442\u0440\u043e\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043b\u0435\u0432\u043e\u0432\u044b\u0432\u043e\u0434\u0438\u043c\u044b\u0445 \u0446\u0435\u043f\u043e\u0447\u0435\u043a b0,b1..bm. \u0415\u0441\u043b\u0438 bi=a1,a2…ajAB, \u0442\u043e \u043a \u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u043c\u043e\u043c\u0435\u043d\u0442\u0443 \u0430\u043d\u0430\u043b\u0438\u0437\u0430 \u043c\u044b \u0443\u0436\u0435 \u043f\u0440\u043e\u0447\u043b\u0438 \u043f\u0435\u0440\u0432\u044b\u0435 j \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0438 \u0441\u0440\u0430\u0432\u043d\u0438\u043b\u0438 \u0438\u0445 \u0441 \u043f\u0435\u0440\u0432\u044b\u043c\u0438 j \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c\u0438 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 bi. \u0411\u044b\u043b\u043e \u0431\u044b \u0436\u0435\u043b\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c bi+1, \u0437\u043d\u0430\u044f \u0442\u043e\u043b\u044c\u043a\u043e a1,a2…aj (\u0447\u0430\u0441\u0442\u044c \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u0446\u0435\u043f\u043e\u0447\u043a\u0438, \u0441\u0447\u0438\u0442\u0430\u043d\u043d\u0443\u044e \u043a \u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u043c\u043e\u043c\u0435\u043d\u0442\u0443), \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 (\u0430]+1aj+2..aj+k \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u043a) \u0438 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b \u0410. \u0415\u0441\u043b\u0438 \u044d\u0442\u0438 \u0442\u0440\u0438 \u0444\u0430\u043a\u0442\u043e\u0440\u0430 \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0442, \u043a\u0430\u043a\u043e\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043d\u0430\u0434\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0434\u043b\u044f \u0440\u0430\u0437\u0432\u0435\u0440\u0442\u043a\u0438 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u0430 \u0410, \u0442\u043e ai+1 \u0442\u043e\u0447\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e ai \u0438 k \u0432\u0445\u043e\u0434\u043d\u044b\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c aj+1aj+2…aj+k .
\n\u0413\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043a\u0430\u0436\u0434\u044b\u0439 \u043b\u0435\u0432\u044b\u0439 \u0432\u044b\u0432\u043e\u0434 \u043e\u0431\u043b\u0430\u0434\u0430\u0435\u0442 \u044d\u0442\u0438\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c, \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f LL(\u043a)-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u043e\u0439. \u041c\u044b \u0443\u0432\u0438\u0434\u0438\u043c, \u0447\u0442\u043e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043b\u0435\u0432\u044b\u0439 \u0430\u043d\u0430\u043b\u0438\u0437\u0430\u0442\u043e\u0440, \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0438\u0439 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u0414\u0430\u0434\u0438\u043c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0439 :
\n\u041e\u041f\u0420: \u041f\u0443\u0441\u0442\u044c a=xb \u0442\u0430\u043a\u0430\u044f \u043b\u0435\u0432\u043e\u0432\u044b\u0432\u043e\u0434\u0438\u043c\u0430\u044f \u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u0432 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0435 G=(N,E,P,S), \u0447\u0442\u043e \u0445\u0435\u0415*, a b \u043b\u0438\u0431\u043e \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u043e\u043c, \u043b\u0438\u0431\u043e \u043f\u0443\u0441\u0442\u0430\u044f \u0446\u0435\u043f\u043e\u0447\u043a\u0430. \u0411\u0443\u0434\u0435\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u0445 \u0437\u0430\u043a\u043e\u043d\u0447\u0435\u043d\u043d\u043e\u0439 \u0447\u0430\u0441\u0442\u044c\u044e \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u0430, \u0430 b — \u043d\u0435\u0437\u0430\u043a\u043e\u043d\u0447\u0435\u043d\u043d\u043e\u0439 \u0447\u0430\u0441\u0442\u044c\u044e \u0447\u0430\u0441\u0442\u044c\u044e. \u0413\u0440\u0430\u043d\u0438\u0446\u0443 \u043c\u0435\u0436\u0434\u0443 \u0445 \u0438 b \u0431\u0443\u0434\u0435\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u0440\u0443\u0431\u0435\u0436\u043e\u043c.
\n\u041f\u0420\u041c: \u041f\u0443\u0441\u0442\u044c x=abacAaB, \u0442\u043e\u0433\u0434\u0430 abac — \u0437\u0430\u043a\u043e\u043d\u0447\u0435\u043d\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u0445, \u0410\u0430\u0412 — \u043d\u0435\u0437\u0430\u043a\u043e\u043d\u0447\u0435\u043d\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0446\u0435\u043f\u043e\u0447\u043a\u0438. \u0415\u0441\u043b\u0438 x=abc, \u0442\u043e abc — \u0437\u0430\u043a\u043e\u043d\u0447\u0435\u043d\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0438 \u0435 — \u043d\u0435\u0430\u0430\u043a\u043e\u0446\u0447\u0435\u043d\u043d\u0430\u044f-\u0438 \u0440\u0443\u0431\u0435\u0436\u043e\u043c \u0441\u043b\u0443\u0436\u0438\u0442 \u043a\u043e\u043d\u0435\u0446 \u0446\u0435\u043f\u043e\u0447\u043a\u0438.
\n\u0418\u043d\u044b\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438 \u0438\u0434\u0435\u044e LL(k) — \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u044a\u044f\u0441\u043d\u0438\u0442\u044c \u0442\u0430\u043a: \u0435\u0441\u043b\u0438 \u0438\u043c\u0435\u0435\u0442\u0441\u044f \u0443\u0436\u0435 \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u043d\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0446\u0435\u043f\u043e\u0447\u043a\u0438, \u0442\u043e \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0438 \u044d\u0442\u043e\u0433\u043e \u0438 \u0435\u0449\u0435 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u043d\u0435\u0440\u0430\u0437\u043e\u0431\u0440\u0430\u043d\u043d\u044b\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0432\u044b\u0432\u043e\u0434 \u043e \u0442\u043e\u043c, \u043a\u0430\u043a\u043e\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043d\u0435\u043e\u044e\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 \u043f\u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443 \u043d\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 (\u043d\u0435 \u0441\u0447\u0438\u0442\u0430\u044f k \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432) \u043e\u0442 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0432\u044b\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u0438\u0437 \u043d\u0435\u0437\u0430\u043a\u043e\u043d\u0447\u0435\u043d\u043d\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0446\u0435\u043f\u043e\u0447\u043a\u0438. \u0412 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u044d\u0442\u043e\u0442 \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: \u0434\u0435\u0440\u0435\u0432\u043e \u0432\u044b\u0432\u043e\u0434\u0430 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u043a\u043e\u0440\u043d\u044f \u0438 \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043e \u0441\u0432\u0435\u0440\u0445\u0443 \u0432\u043d\u0438\u0437.
\n\u0412\u0432\u043e\u0434\u044f\u0442 \u0444\u0443\u043d\u043a\u0446\u0438\u044e FIRST(x) — \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044e\u0449\u0443\u044e \u043f\u0435\u0440\u0432\u044b\u0445 k \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432. \u041e\u0431\u044b\u0447\u043d\u043e \u043f\u0440\u0438\u043f\u0438\u0441\u044b\u0432\u0430\u044e\u0442 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 k \u0438 G — \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0438 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u043d\u043e \u0438\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0443\u0441\u043a\u0430\u0442\u044c, \u0435\u0441\u043b\u0438 \u044d\u0442\u043e \u043d\u0435 \u0432\u044b\u0437\u043e\u0432\u0435\u0442 \u043d\u0435\u0434\u043e\u0440\u0430\u0437\u0443\u043c\u0435\u043d\u0438\u0439.
\n\u041e\u041f\u0420: \u041a\u0421- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 G=(N,E,P,S) \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f LL(k) — \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u043e\u0439 \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e k, \u0435\u0441\u043b\u0438 \u0438\u0437 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u0438\u044f \u0434\u0432\u0443\u0445 \u043b\u0435\u0432\u044b\u0445 \u0432\u044b\u0432\u043e\u0434\u043e\u0432
\n(1) S ?wAa’ ?wb’ a’ ?wx
\n(2) S=\u00bbwAa’?wc’a’?wy
\n\u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u044b\u0445 FIRST(x)=FIRST(y), \u0432\u044b\u0442\u0435\u043a\u0430\u0435\u0442 \u0447\u0442\u043e \u042c’=\u0441’.
\n\u0418\u043d\u0430\u0447\u0435 \u044d\u0442\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0432\u044b\u0440\u0430\u0436\u0430\u0435\u0442 \u0442\u043e, \u0447\u0442\u043e \u0434\u043b\u044f \u0438\u043c\u0435\u044e\u0449\u0435\u0439\u0441\u044f \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u0438 \u0437\u043d\u0430\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 k \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0432\u044b\u0432\u043e\u0434\u0430. \u0413\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f LL- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u043e\u0439, \u0435\u0441\u043b\u0438 \u043e\u043d\u0430 LL(k)-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e k.
\n\u041f\u0420\u041c: \u041f\u0443\u0441\u0442\u044c G \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043f\u0440\u0430\u0432\u0438\u043b S?aAS|b, A?a|bSA. \u0418\u043d\u0442\u0443\u0438\u0442\u0438\u0432\u043d\u043e G \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f LL(1)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u043e\u0439, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e, \u043a\u043e\u043b\u044c \u0441\u043a\u043e\u0440\u043e \u0434\u0430\u043d \u0441\u0430\u043c\u044b\u0439 \u043b\u0435\u0432\u044b\u0439 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b \u0421 \u0432 \u043b\u0435\u0432\u043e\u0432\u044b\u0432\u043e\u0434\u0438\u043c\u043e\u0439 \u0446\u0435\u043f\u043e\u0447\u043a\u0435 \u0438 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0441, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0430, \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c\u043e\u0433\u043e \u043a \u0421 \u0438 \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0449\u0435\u0433\u043e \u043a \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0446\u0435\u043f\u043e\u0447\u043a\u0435, \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0449\u0435\u0439\u0441\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u043c \u0441. \u041f\u0435\u0440\u0435\u0445\u043e\u0434\u044f \u043a \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044e LL(1)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438, \u043c\u044b \u0432\u0438\u0434\u0438\u043c, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 S?wSa’?wb’a’?wx \u0438 S?wSa»?wc’a’?wy \u0438 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u0445 \u0438 \u0443 \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0442\u0441\u044f \u043e\u0434\u043d\u0438\u043c \u0438 \u0442\u0435\u043c \u0436\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u043c , \u0442\u043e \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u042c’=\u0441’. \u0412 \u0434\u0430\u043d\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0435\u0441\u043b\u0438 \u0445 \u0438 \u0443 \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0442\u0441\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u043c \u0430, \u0442\u043e \u0432 \u0432\u044b\u0432\u043e\u0434\u0435 \u0443\u0447\u0430\u0441\u0442\u0432\u043e\u0432\u0430\u043b\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u043e S?aAS \u0438 b’=c’=aAS. \u0410\u043b\u044c\u0442\u0435\u0440\u043d\u0430\u0442\u0438\u0432\u0430 S?b \u0437\u0434\u0435\u0441\u044c \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u0430. \u0421 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b, \u0435\u0441\u043b\u0438 \u0445 \u0438 \u0443 \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0442\u0441\u044f \u0441 b, \u0442\u043e \u0434\u043e\u043b\u0436\u043d\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0442\u044c\u0441\u044f \u043f\u0440\u0430\u0432\u0438\u043b\u043e S\u2014>b \u0438 \u042c’=\u0441’=\u042c. \u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u0441\u043b\u0443\u0447\u0430\u0439 \u0445=\u0443=\u0435 \u0437\u0434\u0435\u0441\u044c \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u0435\u043d, \u0442\u0430\u043a \u043a\u0430\u043a \u0438\u0437 S \u0432 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0435 G \u043d\u0435 \u0432\u044b\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u0435.
\n\u041a\u043e\u0433\u0434\u0430 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0434\u0432\u0430 \u0432\u044b\u0432\u043e\u0434\u0430 S?wAa’?wc’a’?wy \u0440\u0430\u0441\u0441\u0443\u0436\u0434\u0435\u043d\u0438\u0435 \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e. \u0413\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 G \u0441\u043b\u0443\u0436\u0438\u0442 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u043c \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u043e\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 LL(1)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 (\u0438\u043b\u0438 \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0439 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438).
\n\u041e\u041f\u0420: \u041a\u0421-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 G=(N,E,P,S) \u0431\u0435\u0437 \u0435-\u043f\u0440\u0430\u0432\u0438\u043b \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0439 LL(k) — \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u043e\u0439 ( \u0438\u043b\u0438 \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0439 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u043e\u0439 ), \u0435\u0441\u043b\u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e AeN \u0432\u0441\u0435 \u0435\u0433\u043e \u0430\u043b\u044c\u0442\u0435\u0440\u043d\u0430\u0442\u0438\u0432\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0442\u0441\u044f \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c\u0438.
\n\u041f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0440\u0430\u0437\u0431\u043e\u0440\u0430.
\n\u0420\u0430\u0437\u0431\u043e\u0440 \u0434\u043b\u044f LL(k)-rpa\u043c\u043ca\u0442\u0438\u043a\u0438 \u043e\u0447\u0435\u043d\u044c \u0443\u0434\u043e\u0431\u043d\u043e \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0442\u044c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u043e\u0433\u043e k-\u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u043a\u0447\u0446\u0435\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0440\u0430\u0437\u0431\u043e\u0440\u0430, k-\u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0432\u0445\u043e\u0434\u043d\u0443\u044e \u043b\u0435\u043d\u0442\u0443, \u043c\u0430\u0433\u0430\u0437\u0438\u043d \u0438 \u0432\u044b\u0445\u043e\u0434\u043d\u0443\u044e \u043b\u0435\u043d\u0442\u0443. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u044b\u0442\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0441\u043b\u0435\u0434\u0438\u0442\u044c \u0432\u044b\u0432\u043e\u0434 \u0446\u0435\u043f\u043e\u0447\u043a\u0438, \u0437\u0430\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0439 \u043d\u0430 \u0435\u0433\u043e \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u043b\u0435\u043d\u0442\u0435. \u041f\u0440\u0438 \u0447\u0442\u0435\u043d\u0438\u0438 \u0430\u043d\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u043c\u043e\u0439 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u0432\u0445\u043e\u0434\u043d\u0430\u044f \u0433\u043e\u043b\u043e\u0432\u043a\u0430 \u043c\u043e\u0436\u0435\u0442 \u00ab\u0437\u0430\u0433\u043b\u044f\u0434\u044b\u0432\u0430\u0442\u044c\u00bb \u0432\u043f\u0435\u0440\u0435\u0434 \u043d\u0430 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u044b\u0435 k \u0441\u0438\u043c\u0432\u043e\u043b\u0430. \u042d\u0442\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0430\u0432\u0430\u043d\u0446\u0432\u043f\u043e\u0447\u043a\u043e\u0439. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u043c\u0435\u0435\u0442 \u043a\u043e\u043d\u0444\u0438\u0433\u0443\u0440\u0430\u0446\u0438\u044e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c\u0443\u044e \u0442\u0440\u043e\u0439\u043a\u043e\u0439 (\u0445,\u0425\u0430,n), \u0433\u0434\u0435
\n\u0445 — \u043d\u0435\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u0446\u0435\u043f\u043e\u0447\u043a\u0438
\n\u0425\u0430 — \u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u0432 \u043c\u0430\u0433\u0430\u0437\u0438\u043d\u0435 \u0438 \u0425 — \u0432\u0435\u0440\u0445\u043d\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b
\nn — \u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u043d\u0430 \u0432\u044b\u0445\u043e\u0434\u043d\u043e\u0439 \u043b\u0435\u043d\u0442\u0435
\n\u0420\u0430\u0431\u043e\u0442\u043e\u0439 k- \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0440\u0443\u043a\u043e\u0432\u043e\u0434\u0438\u0442 \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0430\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0437\u0430\u0434\u0430\u0435\u0442 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c
\n{(\u0432\u0435\u0440\u0445\u043d\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u043c\u0430\u0433\u0430\u0437\u0438\u043d\u0430)\u0425(\u0430\u0432\u0430\u043d\u0446\u0435\u043f\u043e\u0447\u043a\u0430)}
\n\u0438 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c
\n{(\u043f\u0440\u0430\u0432\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0438 \u0435\u0433\u043e \u043d\u043e\u043c\u0435\u0440)|\u043e\u0448\u0438\u0431\u043a\u0430|\u0432\u044b\u0431\u0440\u043e\u0441|\u0434\u043e\u043f\u0443\u0441\u043a}.
\n\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u044b\u043c \u0434\u043b\u044f \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438, \u0435\u0441\u043b\u0438 \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0439 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u0438\u0437 \u044d\u0442\u043e\u0439 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u043f\u0440\u0430\u0432\u0438\u043b \u0434\u043b\u044f \u0435\u0435 \u0440\u0430\u0437\u0431\u043e\u0440\u0430. \u0415\u0441\u043b\u0438 \u0440\u0430\u0431\u043e\u0442\u043e\u0439 \u043d\u0435\u043a\u043e\u0435\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0440\u0443\u043a\u043e\u0432\u043e\u0434\u0438\u0442 \u043a\u0430\u043a\u0430\u044f-\u0442\u043e \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0438 \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u044b\u043c \u0434\u043b\u044f \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0439 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438, \u0442\u043e \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0439.
\n\u041f\u0420\u041c:
\n\u041f\u0443\u0441\u0442\u044c \u0434\u0430\u043d\u0430 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 \u0441 \u043f\u0440\u0430\u0432\u0438\u043b\u0430\u043c\u0438 :
\n(1) S?aAS
\n(2) S?b
\n(3) A?a
\n(4) A?bSA
\n\u0414\u043b\u044f \u0442\u0430\u043a\u043e\u0439 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0430 \u0442\u0430\u0431\u043b\u0438\u0446\u0430:
\n\u0430\u0432\u0430\u043d\u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u0430 \u042c \u0435
\n\u0432\u0435\u0440\u0445\u043d\u0438\u0439 S aAS,1 \u042c,2 \u043e\u0448\u0438\u0431\u043a\u0430 \u0441\u0438\u043c\u0432\u043e\u043b \u0410 \u0430,3 bSA,4 \u043e\u0448\u0438\u0431\u043a\u0430 \u043c\u0430\u0433\u0430\u0437\u0438\u043d\u0430 \u0430 \u0432\u044b\u0431\u0440\u043e\u0441 \u043e\u0448\u0438\u0431\u043a\u0430 \u043e\u0448\u0438\u0431\u043a\u0430
\n\u042c \u043e\u0448\u0438\u0431\u043a\u0430 \u0432\u044b\u0431\u0440\u043e\u0441 \u043e\u0448\u0438\u0431\u043a\u0430 $ \u043e\u0448\u0438\u0431\u043a\u0430 \u043e\u0448\u0438\u0431\u043a\u0430 \u0434\u043e\u043f\u0443\u0441\u043a \u041f\u043e \u0442\u0430\u043a\u043e\u0439 \u0442\u0430\u0431\u043b\u0438\u0446\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0432\u0435\u0434\u0435\u043d \u0430\u043d\u0430\u0434\u0438\u0437 (abbab,S$,e) -(abbab,aAS$,1)
\n-( bbab,AS$,1)
\n-( bbab,bSAS$,14)
\n-( bab,SAS$,14)
\n-( bab,bAS$,142)
\n-( ab,AS$,142)
\n-(ab,aS$,1423) \t\t-(b,S$,1423) \t\t-(b,b$,14232) \t\t-(e,$,14232)
\nk- \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u041a\u0421-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 G \u043c\u043e\u0436\u043d\u043e \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043d\u0430 \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u041c\u041f-\u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435 \u0441 \u043a\u043e\u043d\u0446\u0435\u0432\u044b\u043c \u043c\u0430\u0440\u043a\u0435\u0440\u043e\u043c \u043d\u0430 \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u043b\u0435\u043d\u0442\u0435. \u0422\u0430\u043a \u043a\u0430\u043a \u0432\u0445\u043e\u0434\u043d\u0430\u044f \u0433\u043e\u043b\u043e\u0432\u043a\u0430 \u041c\u041f- \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f \u043c\u043e\u0436\u0435\u0442 \u043e\u0431\u043e\u0437\u0440\u0435\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u0438\u043d \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u0441\u0438\u043c\u0432\u043e\u043b, \u0430\u0432\u0430\u043d\u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0445\u0440\u0430\u043d\u0438\u0442\u044c\u0441\u044f \u0432 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438 \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0435\u0433\u043e \u0443\u0441\u0442\u0440\u043e\u0439\u0441\u0442\u0432\u0430. \u041e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u0434\u0435\u0442\u0430\u043b\u0438 \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b.
\n\u0422\u0420\u041c: \u041f\u0443\u0441\u0442\u044c \u0410 — k- \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u0434\u043b\u044f \u041a\u0421-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 G. \u0422\u043e\u0433\u0434\u0430 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0442\u0430\u043a\u043e\u0439 \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u041c\u041f- \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u0442\u044c \u043b\u044e\u0431\u0443\u044e \u0446\u0435\u043f\u043e\u0447\u043a\u0443 \u0438\u0437 \u044d\u0442\u043e\u0439 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438. \u0418\u043d\u0430\u0447\u0435 \u0433\u043e\u0432\u043e\u0440\u044f \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043b\u044e\u0431\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430 \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u043c \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435.
\n\u0421\u041b\u0412: \u041f\u0443\u0441\u0442\u044c \u0410 — k- \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u0434\u043b\u044f \u041a\u0421-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 G. \u0422\u043e\u0433\u0434\u0430 \u0434\u043b\u044f G \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043b\u0435\u0432\u044b\u0439 \u0430\u043d\u0430\u043b\u0438\u0437\u0430\u0442\u043e\u0440.
\n\u0421\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f LL(k)-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438.
\n\u041f\u043e\u043a\u0430\u0436\u0435\u043c \u0447\u0442\u043e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 LL(k) \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u043c\u043e\u0436\u043d\u043e \u043c\u0435\u0445\u0430\u043d\u0438\u0447\u0435\u0441\u043a\u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u044b\u0439 k- \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0437\u0431\u043e\u0440\u0430. \u0422\u0430\u043a \u043a\u0430\u043a \u044f\u0434\u0440\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0430\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u0430, \u043d\u0430\u0434\u043e \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c, \u043a\u0430\u043a \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043f\u043e \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0435 \u0442\u0430\u043a\u0443\u044e \u0442\u0430\u0431\u043b\u0438\u0446\u0443. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0432\u044b\u0432\u0435\u0434\u0435\u043c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438.
\n\u0412 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0438 LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0434\u043b\u044f \u0434\u0430\u043d\u043d\u043e\u0439 \u0432\u044b\u0432\u043e\u0434\u0438\u043c\u043e\u0439 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 wAa \u0446\u0435\u043f\u043e\u0447\u043a\u0430 w \u0438 \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0437\u0430 \u043d\u0435\u0439 k \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0442, \u043a\u0430\u043a\u043e\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u0434\u043b\u044f \u0440\u0430\u0437\u0432\u0435\u0440\u0442\u043a\u0438 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u0430 \u0410. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0430 \u043f\u0435\u0440\u0432\u044b\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c\u0441\u044f, \u0447\u0442\u043e \u0434\u043b\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0443\u0436\u043d\u043e\u0433\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u043d\u0430\u0434\u043e \u043f\u043e\u043c\u043d\u0438\u0442\u044c \u0432\u0441\u044e \u0446\u0435\u043f\u043e\u0447\u043a\u0443 w. \u041e\u0434\u043d\u0430\u043a\u043e \u044d\u0442\u043e \u043d\u0435 \u0442\u0430\u043a. \u0414\u043e\u043a\u0430\u0436\u0435\u043c \u0442\u0435\u043e\u0440\u0435\u043c\u0443, \u043e\u0447\u0435\u043d\u044c \u0432\u0430\u0436\u043d\u0443\u044e \u0434\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f LL(k)-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a:
\n\u0422\u0420\u041c: \u041a\u0421-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 G=(N,E,P,S) \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f LL(k)-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u043e\u0439 \u0442\u043e\u0433\u0434\u0430 \u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0433\u0434\u0430, \u043a\u043e\u0433\u0434\u0430 \u0434\u043b\u044f \u0434\u0432\u0443\u0445 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043f\u0440\u0430\u0432\u0438\u043b \u0410?\u042c’ \u0438 \u0410-\u043c;’ \u0438\u0437 \u0420 \u043f\u0435\u0440\u0435\u0441\u0435\u0447\u0435\u043d\u0438\u0435 FIRST(b’a’)^FIRST(c»a’) \u043f\u0443\u0441\u0442\u043e \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0442\u0430\u043a\u0438\u0445 wAa’, \u0447\u0442\u043e S?wAa’.
\n\u0414\u041a\u0412: \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0447\u0442\u043e w, \u0410, \u0430’, \u042c’ \u0438 \u0441’ \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u044e\u0442 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u043c \u0442\u0435\u043e\u0440\u0435\u043c\u044b, \u0430 FIRST(b’a’)nFIRST(c’a’) \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0445. \u0422\u043e\u0433\u0434\u0430 \u043f\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044e FIRST \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443 \u0438 z \u043d\u0430\u0439\u0434\u0443\u0442\u0441\u044f \u0432\u044b\u0432\u043e\u0434\u044b S?wAa’?wb’a’?wxy \u0438 S?wAa’?wc’a’?wx2. (\u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u0437\u0434\u0435\u0441\u044c \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0438 \u0442\u043e\u0442 \u0444\u0430\u043a\u0442, \u0447\u0442\u043e N \u043d\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0431\u0435\u0441\u043f\u043e\u043b\u0435\u0437\u043d\u044b\u0445 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u043e\u0432, \u043a\u0430\u043a \u044d\u0442\u043e \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u044b\u0445 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a.) \u0415\u0441\u043b\u0438 |\u0445| < k \u0442\u043e \u0443 = z = \u0435. \u0422\u0430\u043a \u043a\u0430\u043a \u042c’ <> \u0441’, \u0442\u043e G \u043d\u0435 LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430.
\n\u0414\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0447\u0442\u043e G \u043d\u0435 LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430. \u0422\u043e\u0433\u0434\u0430 \u043d\u0430\u0439\u0434\u0443\u0442\u0441\u044f \u0442\u0430\u043a\u0438\u0435 \u0434\u0432\u0430 \u0432\u044b\u0432\u043e\u0434\u0430 S?wAa’?wb’a’?wx \u0438 S?wAa’?wc’a’?wy, \u0447\u0442\u043e \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u0445 \u0438 \u0443 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0442 \u0432 \u043f\u0435\u0440\u0432\u044b\u0445 k \u043f\u043e\u0437\u0438\u0446\u0438\u044f\u0445, \u043d\u043e b'<>c’. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0410?\u042c’ \u0438 \u0410?\u0441’ — \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0438\u0437 \u0420 \u0438 \u043a\u0430\u0436\u0434\u043e\u0435 \u0438\u0437 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 FIRST(b’a’) \u0438 FIRST(c’a’) \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0446\u0435\u043f\u043e\u0447\u043a\u0443 FIRST(x) \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0443\u044e \u0441 FIRST(y). \u0427\u0422\u0414.
\n\u041f\u0420\u041c: \u0413\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 G \u0438\u0437 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 S?aS|a, \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 LL(1)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u043e\u0439, \u0442\u0430\u043a \u043a\u0430\u043a FIRST1(aS)=FIRST1(a)=a. \u042d\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u044a\u044f\u0441\u043d\u0438\u0442\u044c \u0442\u0430\u043a — \u0432\u0438\u0434\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0435\u0440\u0432\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043a\u0430\u043a\u043e\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c (\u043b\u0435\u0432\u043e\u0435 \u0438\u043b\u0438 \u043f\u0440\u0430\u0432\u043e\u0435). \u0421 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b \u044d\u0442\u0430 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f LL2(k) \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u043e\u0439 — \u0447\u0442\u043e \u0432\u043f\u043e\u043b\u043d\u0435 \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e.
\n\u041e\u041f\u0420: \u041f\u0443\u0441\u0442\u044c G=(N,E,P,S) — \u041a\u0421-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430. \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c FOLLOWk(b’) \u043a\u0430\u043a \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0433\u0443\u0442 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0442\u044c\u0441\u044f \u043f\u043e\u0441\u043b\u0435 \u043d\u0435\u0442\u0435\u043c\u0438\u043d\u0430\u043b\u0430, \u044f\u0432\u043b\u044f\u044e\u0449\u0435\u0433\u043e\u0441\u044f \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u043e\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u0438.
\n\u0422\u0420\u041c: \u041a\u0421-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 G=(N,E,P,S) \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f LL(1)-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u043e\u0439 \u0442\u043e\u0433\u0434\u0430 \u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0433\u0434\u0430, \u043a\u043e\u0433\u0434\u0430 \u0434\u043b\u044f \u0434\u0432\u0443\u0445 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043f\u0440\u0430\u0432\u0438\u043b \u0410-\u00bb\u042c’ \u0438 \u0410?\u0441’ \u043f\u0435\u0440\u0435\u0441\u0435\u0447\u0435\u043d\u0438\u0435 FIRST1(b’ FOLLOW1 (A))^FIRST1 (\u0441’ FOLLOW1(A)) \u043f\u0443\u0441\u0442\u043e \u043f\u0440\u0438 \u0432\u0441\u0435\u0445 AeN. (\u0411\u0435\u0437\u0414\u041a\u0412).
\n\u0422\u0435\u043e\u0440\u0435\u043c\u0443 \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0440\u0430\u0437\u0438\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c : \u043f\u043e \u043f\u0435\u0440\u0432\u043e\u043c\u0443 \u0441\u0438\u043c\u0432\u043e\u043b\u0443 \u043f\u043e\u0441\u043b\u0435 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u0430 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c\u043e\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e — \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u044d\u0442\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b \u0438 \u043f\u0435\u0440\u0435\u0441\u0435\u0447\u0435\u043d\u0438\u0435 \u043f\u0443\u0441\u0442\u043e. \u042d\u0442\u0430 \u0442\u0435\u043e\u0440\u0435\u043c\u0430 \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0442\u044c\u0441\u044f \u043a LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430\u043c, \u043d\u043e \u043d\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c\u0441\u044f. \u0413\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u0435\u043e\u0440\u0435\u043c\u0430 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0441\u0438\u043b\u044c\u043d\u044b\u043c\u0438, \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0432\u0441\u0435 LL(1) \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 — \u0441\u0438\u043b\u044c\u043d\u044b\u0435. \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0442\u0430\u043a \u0436\u0435 \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c \u0447\u0442\u043e \u043a\u0430\u0436\u0434\u0430\u044f LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0435\u0441\u043b\u0438 \u0438\u043c\u0435\u0435\u0442\u0441\u044f \u043d\u0435\u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u0430\u044f \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 — \u0442\u043e \u043e\u043d\u0430 \u043d\u0435 LL(k). \u0418\u043c\u0435\u0435\u0442\u0441\u044f \u043d\u0435\u0440\u0430\u0437\u0440\u0435\u0448\u0438\u043c\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0440\u0430\u0441\u043f\u043e\u0437\u043d\u0430\u0432\u0430\u043d\u0438\u044f, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043b\u0438 \u0434\u043b\u044f \u0434\u0430\u043d\u043d\u043e\u0439 \u041a\u0421-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 G, \u043d\u0435 \u044f\u0432\u043b\u044f\u044e\u0449\u0435\u0439\u0441\u044f LL(k), \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u0430\u044f \u0435\u0439 LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430. \u041e\u0434\u043d\u0430\u043a\u043e \u0432 \u0440\u044f\u0434\u0435 \u0441\u043b\u0443\u0447\u0430\u0435\u0432 \u0442\u0430\u043a\u043e\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e. \u041f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0434\u0432\u0430 \u0441\u043f\u043e\u0441\u043e\u0431\u0430:
\n\u041f\u0435\u0440\u0432\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 — \u0443\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043b\u0435\u0432\u043e\u0439 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438.
\n\u041f\u0420\u041c: \u041f\u0443\u0441\u0442\u044c G — \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 S?Sa|b \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f LL- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u043e\u0439. \u0417\u0430\u043c\u0435\u043d\u0438\u043c \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435:
\nS ?bS’
\nS’?aS’|e \u043f\u043e\u043b\u0443\u0447\u0438\u0432 \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u0443\u044e LL(1)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0443.
\n\u0414\u0440\u0443\u0433\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 — \u043b\u0435\u0432\u0430\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f.
\n\u041f\u0420\u041c: \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c LL(2)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0443 G \u0441 \u0434\u0432\u0443\u043c\u044f \u043f\u0440\u0430\u0432\u0438\u043b\u0430\u043c\u0438 S?aS|a. \u0412 \u044d\u0442\u0438\u0445 \u0434\u0432\u0443\u0445 \u043f\u0440\u0430\u0432\u0438\u043b\u0430\u0445 \u00ab\u0432\u044b\u043d\u0435\u0441\u0435\u043c \u0432\u043b\u0435\u0432\u043e \u0437\u0430 \u0441\u043a\u043e\u0431\u043a\u0438\u00bb \u0441\u0438\u043c\u0432\u043e\u043b \u0430, \u0437\u0430\u043f\u0438\u0441\u0430\u0432 \u0438\u0445 \u0432 \u0432\u0438\u0434\u0435 S\u2014>a(S|e). \u0418\u043d\u044b\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u043c\u044b \u0441\u0447\u0438\u0442\u0430\u0435\u043c \u0447\u0442\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043a\u043e\u043d\u043a\u0430\u0442\u0435\u043d\u0430\u0446\u0438\u0438 \u0434\u0438\u0441\u0442\u0440\u0438\u0431\u0443\u0442\u0438\u0432\u043d\u0430 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432\u044b\u0431\u043e\u0440\u0430 \u0430\u043b\u0442\u0435\u0440\u043d\u0430\u0442\u0438\u0432\u044b (\u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u0435\u043c\u043e\u0439 \u0432\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u044c\u043d\u043e\u0439 \u0447\u0435\u0440\u0442\u043e\u0439). \u0417\u0430\u043c\u0435\u043d\u0438\u043c \u044d\u0442\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u043d\u0430 :
\nS?aA
\nA?S|e \u0442\u0435\u043c \u0441\u0430\u043c\u044b\u043c \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u0443\u044e LL(1)-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0443.
\n\u0420\u0430\u0437\u0431\u043e\u0440 \u0434\u043b\u044f LL(1)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a.
\n\u042f\u0434\u0440\u043e\u043c \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0430\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u0430. \u0412 \u044d\u0442\u043e\u043c \u0438 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0440\u0430\u0437\u0434\u0435\u043b\u0430\u0445 \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043e \u043a\u0430\u043a \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u0443\u044e \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0443\u044e \u0442\u0430\u0431\u043b\u0438\u0446\u0443. \u0410\u041b\u0413 1: \u0423\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0430\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0434\u043b\u044f LL(1)-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438. \u0412\u0445\u043e\u0434 : LL(1)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 . \u0412\u044b\u0445\u043e\u0434 : \u041a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u0430\u044f \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0430\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u0430. \u041c\u0435\u0442\u043e\u0434 : \u0411\u0443\u0434\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e $-\u043c\u0430\u0440\u043a\u0435\u0440 \u0434\u043d\u0430 \u043c\u0430\u0433\u0430\u0437\u0438\u043d\u0430. \u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:
\n(1) \u0415\u0441\u043b\u0438 \u0410 -\u00bb \u0430’ — \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u0438\u0437 \u0420 \u0441 \u043d\u043e\u043c\u0435\u0440\u043e\u043c i, \u0442\u043e M[A,a]=(a’,i) \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0430<>\u0435, \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0430\u0449\u0438\u0445 FIRSTI(a’). \u0415\u0441\u043b\u0438 eeFIRST-Ka’), \u0442\u043e M[A,b]=(a’,i) \u0434\u043b\u044f \u0432\u0441\u0435\u0445 beFOLLOWI(A).
\n(2) \u041c[\u0430,\u0430]=\u0432\u044b\u0431\u0440\u043e\u0441 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0430\u0435\u0415.
\n(3) \u041c[$,\u0435]=\u0434\u043e\u043f\u0443\u0441\u043a.
\n(4) \u0412 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u041c[\u0425,\u0430]=\u043e\u0448\u0438\u0431\u043a\u0430 \u0434\u043b\u044f XeNUEU{$} \u0438 \u0430\u0435\u0415U{\u0435}.
\n\u0422\u0420\u041c: \u041f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0442\u0440\u043e\u0438\u0442 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u0443\u044e \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0443\u044e \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0434\u043b\u044f LL(1)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u041e.
\n\u0420\u0430\u0437\u0431\u043e\u0440 \u0434\u043b\u044f LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a.
\n\u041f\u043e\u0441\u0442\u0440\u043e\u0438\u043c \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0443\u044e \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0434\u043b\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0439 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438. \u0415\u0441\u043b\u0438 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 \u0441\u0438\u043b\u044c\u043d\u0430\u044f, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441 \u0430\u0432\u0430\u043d\u0446\u0435\u043f\u043e\u0447\u043a\u0430\u043c\u0438 \u0440\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u043d\u044b\u043c\u0438 \u0434\u043e k \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432. \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u043e\u0431\u043b\u0435\u043c. \u0412 1-\u043c \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u0432 \u043c\u0430\u0433\u0430\u0437\u0438\u043d \u043f\u043e\u043c\u0435\u0449\u0430\u043b\u0438\u0441\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0438\u0437 EuN \u0438 \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u043b\u043e\u0441\u044c, \u0447\u0442\u043e \u0434\u043b\u044f \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e\u0433\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c\u043e\u0433\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0437\u043d\u0430\u0442\u044c \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u043d\u0430\u0432\u0435\u0440\u0445\u0443 \u043c\u0430\u0433\u0430\u0437\u0438\u043d\u0430 \u0438 \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u0441\u0438\u043c\u0432\u043e\u043b. \u0414\u043b\u044f \u043d\u0435 \u0441\u0438\u043b\u044c\u043d\u044b\u0445 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a \u044d\u0442\u043e\u0433\u043e \u043c\u043e\u0436\u0435\u0442 \u043e\u043a\u0430\u0437\u0430\u0442\u044c\u0441\u044f \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e.
\n\u041f\u0420\u041c: \u0412\u043e\u0437\u044c\u043c\u0435\u043c \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0443
\nS\u2014>aAaa|bAba
\n\u0410?\u042c|\u0435
\n\u0415\u0441\u043b\u0438 \u0434\u0430\u043d\u044b \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b \u0410 \u0438 \u0430\u0432\u0430\u043d\u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u042c\u0430, \u0442\u043e \u043d\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u043a\u0430\u043a\u043e\u0435 \u0438\u0437 \u043f\u0440\u0430\u0432\u0438\u043b \u043d\u0430\u0434\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c.
\n\u041d\u0435\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u0442\u0430\u043a\u043e\u0433\u043e \u0440\u043e\u0434\u0430 \u043e\u0434\u043d\u0430\u043a\u043e \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u0440\u0435\u0448\u0438\u0442\u044c, \u0441\u0432\u044f\u0437\u0430\u0432 \u0441 \u043a\u0430\u0436\u0434\u044b\u043c \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u043e\u043c \u0438 \u0447\u0430\u0441\u0442\u044c\u044e \u043b\u0435\u0432\u043e\u0432\u044b\u0432\u043e\u0434\u0438\u043c\u043e\u0439 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 (\u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u0436\u0435\u0442 \u043e\u043a\u0430\u0437\u0430\u0442\u044c\u0441\u044f \u0441\u043f\u0440\u0430\u0432\u0430), \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b, \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u044b\u0439 LL(k)-\u0442\u0430\u0431\u043b\u0438\u0446\u0435\u0439. \u041f\u043e \u0434\u0430\u043d\u043d\u043e\u0439 \u0430\u0432\u0430\u043d\u0446\u0435\u043f\u043e\u0447\u043a\u0435 LL(k)- \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0431\u0443\u0434\u0435\u0442 \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c \u043a\u0430\u043a\u043e\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043d\u0430\u0434\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u043d\u0430 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u043c \u0448\u0430\u0433\u0435 \u0432\u044b\u0432\u043e\u0434\u0430.
\n\u041e\u041f\u0420: \u041f\u0443\u0441\u0442\u044c \u0415 — \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0430\u043b\u0444\u0430\u0432\u0438\u0442. \u0415\u0441\u043b\u0438 L1 \u0438 L2 — \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0415, \u0442\u043e \u043f\u043e\u043b\u043e\u0436\u0438\u043c L1 \u00aek L2 = {
\nw | \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 xeL1 \u0438 yeL.2
\n\u043b\u0438\u0431\u043e w = \u0445\u0443, \u0435\u0441\u043b\u0438 [\u0445\u0443| <=k
\n\u043b\u0438\u0431\u043e w \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043f\u0435\u0440\u0432\u044b\u0445 k \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u0445\u0443
\n} \u041b\u041c\u0410: \u0414\u043b\u044f \u043b\u044e\u0431\u043e\u0439 \u041a\u0421- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 G=(N,E,P,S) \u0438 \u043b\u044e\u0431\u044b\u0445 a’, b’e(NuE):
\nFIRSTk(a’b’)=FIRSTk(a’) \u00a9k FIRSTk(b’)
\n\u041e\u041f\u0420: \u041f\u0443\u0441\u0442\u044c G=(N,E,P,S) — \u041a\u0421- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430. \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u044b\u0445 AeN \u0438 LcE \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c LL(k)- \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0422\u0430,1, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0443\u044e \u0410 \u0438 L, \u043a\u0430\u043a \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0422(\u0438), \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0441\u043b\u0443\u0436\u0438\u0442 :
\n(1)\t=\u043e\u0448\u0438\u0431\u043a\u0430, \u0435\u0441\u043b\u0438 \u0432 \u0420 \u043d\u0435\u0442 \u0442\u0430\u043a\u043e\u0433\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0410-*\u0430’, \u0447\u0442\u043e FIRSTk(a’) \u00aek L \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 u;
\n(2)\t=(A?a’,<Y1,Y2…Ym>), \u0435\u0441\u043b\u0438 \u0410?\u0430’ — \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u0438\u0437 \u0420, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e FlRSTk(a’) \u00aek L
\n\u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 u;
\n(3) \u043d\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043e, \u0435\u0441\u043b\u0438 \u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 \u043d\u0430\u0439\u0434\u0443\u0442\u0441\u044f \u0434\u0432\u0430 \u0438 \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 (\u044d\u0442\u0443 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u043a\u043e\u043d\u0444\u043b\u0438\u043a\u0442\u043e\u043c \u043c\u0435\u0436\u0434\u0443 \u043f\u0440\u0430\u0432\u0438\u043b\u0430\u043c\u0438)
\n\u041d\u0430 \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e\u043c \u044f\u0437\u044b\u043a\u0435 \u044d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u0447\u0442\u043e \u0432\u044b\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043e\u0448\u0438\u0431\u043a\u0430, \u0435\u0441\u043b\u0438 u \u0432\u043e\u043e\u0431\u0449\u0435 \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0446\u0435\u043f\u043e\u0447\u043a\u043e\u0439 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438, \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u0435\u0441\u043b\u0438 \u043e\u043d\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u043d\u043e \u0438 \u0435\u0441\u043b\u0438 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0430\u0432\u0438\u043b — \u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043d\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f.
\n\u0410\u041b\u0413 2: \u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 LL(k)- \u0442\u0430\u0431\u043b\u0438\u0446.
\n\u0412\u0445\u043e\u0434: LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 G=(N,E,P,S).
\n\u0412\u044b\u0445\u043e\u0434: \u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e TG LL(k)-\u0442\u0430\u0431\u043b\u0438\u0446, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0435\u0439 \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u0434\u043b\u044f G.
\n\u041c\u0435\u0442\u043e\u0434:
\n(1) \u041f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c LL(k)- \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0422\u041e, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0443\u044e S \u0438 {\u0435}.
\n(2) \u041f\u043e\u043b\u043e\u0436\u0438\u0442\u044c \u0432\u043d\u0430\u0447\u0430\u043b\u0435 TG={TO}.
\n(3) \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 LL(k) -\u0442\u0430\u0431\u043b\u0438\u0446\u044b TeTG, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0435\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 T(u)=(A\u2014>xOB1x1…Bmxm,<Y1,Y2…Ym>) \u0432\u043a\u043b\u044e\u0447\u0438\u0442\u044c \u0432 TG LL(k)- \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0422 \u0434\u043b\u044f 1<=i<=m, \u0435\u0441\u043b\u0438 \u0422 \u0435\u0449\u0435 \u043d\u0435 \u0432\u0445\u043e\u0434\u0438\u0442 \u0432 TG.
\n(4) \u041f\u043e\u0432\u0442\u043e\u0440\u044f\u0442\u044c \u0448\u0430\u0433 3 \u043f\u043e\u043a\u0430 \u0432 TG \u043c\u043e\u0436\u043d\u043e \u0432\u043a\u043b\u044e\u0447\u0430\u0442\u044c \u043d\u043e\u0432\u044b\u0435 \u0442\u0430\u0431\u043b\u0438\u0446\u044b.
\n\u041f\u0420\u041c: \u041f\u043e\u0441\u0442\u0440\u043e\u0438\u043c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e LL(2)- \u0442\u0430\u0431\u043b\u0438\u0446 \u0434\u043b\u044f \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 8?\u0430\u0410\u0430\u0430|\u042c\u0410\u042c\u0430 \u0438 \u0410-\u00bb\u042c|\u0435. \u041d\u0430\u0447\u043d\u0435\u043c \u0441 TG={TS,{e}} . \u0422\u0430\u043a \u043a\u0430\u043a TS,{e}(aa)=( S?aAaa,{aa}), \u0442\u043e \u0432 TG \u043d\u0430\u0434\u043e \u0432\u043a\u043b\u044e\u0447\u0438\u0442\u044c \u0422\u0410,{\u0430\u0430}. \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e, \u0442\u0430\u043a \u043a\u0430\u043a T0(bb)=( S?bAba,{ba}), \u0442\u043e \u0432 TG \u043d\u0443\u0436\u043d\u043e \u0442\u0430\u043a\u0436\u0435 \u0432\u043a\u043b\u044e\u0447\u0438\u0442\u044c.-. (\u042d\u043b\u0435\u043c\u0435\u043d\u0442\u044b LL(2)- \u0442\u0430\u0431\u043b\u0438\u0446 \u0422\u0410,{\u0430\u0430} \u0438 \u0422\u0410,{\u042c\u0430}, \u043e\u0442\u043b\u0438\u0447\u043d\u044b\u0435 \u043e\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043e\u0448\u0438\u0431\u043a\u0430, \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u044b \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0435 \u043d\u0438\u0436\u0435). \u0421\u0435\u0439\u0447\u0430\u0441 TG={TS,{e},TA,{aa},TA,{ba}}, \u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0443\u0436\u0435 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0432\u043a\u043b\u044e\u0447\u0438\u0442\u044c \u0432 TG \u043d\u043e\u0432\u044b\u0445 \u0442\u0430\u0431\u043b\u0438\u0446, \u0442\u0430\u043a \u0447\u0442\u043e \u044d\u0442\u043e \u0442\u0440\u0438 LL(2)- \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u043e\u0431\u0440\u0430\u0437\u0443\u044e\u0442 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0435 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0435. \u0422\u0410,{\u0430\u0430} \u0422\u0410,{\u042c\u0430}
\nu \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 u \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430
\n\u042c\u0430 \u0410 ? b — ba A ? \u0435
\n\u0430\u0430 \u0410?\u0435 — \u0430\u0430 \u0410 ? b
\n\u0422\u0435\u043f\u0435\u0440\u044c \u0434\u0430\u0434\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u0443\u044e \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0443\u044e \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u043f\u043e \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u043c\u0443 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0443 LL(k)- \u0442\u0430\u0431\u043b\u0438\u0446. \u0423\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u043c\u044b\u0439 \u044d\u0442\u043e\u0439 \u0442\u0430\u0431\u043b\u0438\u0446\u0435\u0439 k- \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0431\u0443\u0434\u0435\u0442 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043c\u0430\u0433\u0430\u0437\u0438\u043d\u043d\u044b\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0443\u043f\u043e\u0442\u0440\u0435\u0431\u043b\u044f\u0442\u044c \u0432\u043c\u0435\u0441\u0442\u043e \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u043e\u0432 LL(k)-\u0442\u0430\u0431\u043b\u0438\u0446\u044b.
\n\u0410\u041b\u0413 3: \u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0435\u0439 \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u0434\u043b\u044f LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438.
\n\u0412\u0445\u043e\u0434 : LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 \u0438 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e TG LL(k)- \u0442\u0430\u0431\u043b\u0438\u0446.
\n\u0412\u044b\u0445\u043e\u0434 : \u041a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u0430\u044f \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0430\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u041c \u0434\u043b\u044f G.
\n\u041c\u0435\u0442\u043e\u0434: \u041c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 (TGUEu{$})xE*k \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:
\n(1)\u0415\u0441\u043b\u0438 A?xOB1x1…Bmxm — \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u0438\u0437 \u0420 \u0441 \u043d\u043e\u043c\u0435\u0440\u043e\u043c i \u0438 TA.LeTG, \u0442\u043e \u0434\u043b\u044f \u0432\u0441\u0435\u0445 u, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0422\u0410, L(u)=(A-+xOB1x1…Bmxm,<Y1…Ym>) \u043f\u043e\u043b\u0430\u0433\u0430\u0435\u043c M[TA,L,u]=(xOTB1,Y1…TBm,Ymxm,i).
\n(2) \u041c[\u0430,\u0430\u0443]=\u0432\u044b\u0431\u0440\u043e\u0441\u0434\u043b\u044f BcexveE*(k-1).
\n(3) \u041c[$,\u0435]=\u0434\u043e\u043f\u0443\u0441\u043a.
\n(4) \u0412 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u041c[\u0425,u]=\u043e\u0448\u0438\u0431\u043a\u0430
\n(5) TS,{e} — \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u0430\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u0430.
\n\u041f\u0420\u041c: \u041f\u043e\u0441\u0442\u0440\u043e\u0438\u043c \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0443\u044e \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0434\u043b\u044f LL(2)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438
\n(1) S?aAaa
\n(2) S?bAba
\n(3) A?b
\n(4) A?e
\n\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0435 \u0435\u0439 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e LL(2)-\u0442\u0430\u0431\u043b\u0438\u0446, \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u0435 \u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043e\u043b\u0436\u0435\u043d \u0432\u044b\u0434\u0430\u0442\u044c \u0442\u0430\u0431\u043b\u0438\u0446\u0443:
\n\u0430\u0430 ab a ba bb be \u0422\u041e \u0430\u04221\u0430\u0430,1 \u0430\u04221\u0430\u0430,1 \u042c\u04222\u042c\u0430,2 \u04221 \u0435,4 , \u042c,3 \u04222 \u0435,4 \u042c,3 \u0430 \u0432\u044b\u0431\u0440\u043e\u0441 \u0432\u044b\u0431\u0440\u043e\u0441 \u0432\u044b\u0431\u0440\u043e\u0441
\n\u042c \u0432\u044b\u0431\u0440\u043e\u0441 \u0432\u044b\u0431\u0440\u043e\u0441 \u0432\u044b\u0431\u0440\u043e\u0441 $ \u0434\u043e\u043f\u0443\u0441\u043a*
\n\u0433\u0434\u0435 TO=TS,{e}, \u04221=\u0422\u0410,{\u0430\u0430} \u0438 \u04222=\u0422\u0410,{\u042c\u0430}. \u041f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0432 \u043f\u0443\u0441\u0442\u044b\u0445 \u044f\u0447\u0435\u0439\u043a\u0430\u0445 — \u043e\u0448\u0438\u0431\u043a\u0430. \u0414\u043e\u043f\u0443\u0441\u043a* \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0439 \u043a\u043e\u043b\u043e\u043d\u043a\u0435. \u0414\u043b\u044f \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u042c\u042c\u0430 2-\u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u0434\u0430\u0441\u0442 \u0442\u0430\u043a\u0443\u044e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0442\u0430\u043a\u0442\u043e\u0432: ‘ (bba,TO$,e) |-(\u042c\u042c\u0430,\u042c\u04222\u042c\u0430$,2)
\n|- (\u042c\u0430,\u04222\u042c\u0430$,2;
\n|-(\u042c\u0430,\u042c\u0430$,24) \t\t\t|- (\u0430,\u0430$,24) \t\t\tI- (\u0435,$,24)
\n\u0422\u0420\u041c: \u041e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0442\u0440\u043e\u0438\u0442 \u0434\u043b\u044f LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 G=(N,E,P,S) \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u0443\u044e \u0442\u0430\u0431\u043b\u0438\u0446\u0443, \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0443\u044e \u0440\u0430\u0431\u043e\u0442\u043e\u0439 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0433\u043e k- \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.
\n\u041f\u0420\u041c: \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c LL(2)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0443 G \u0441 \u043f\u0440\u0430\u0432\u0438\u043b\u0430\u043c\u0438:
\n(1)S?e
\n(2) S?abA
\n(3) A?Saa
\n(4) A?b
\n\u041f\u043e\u0441\u0442\u0440\u043e\u0438\u043c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 LL(2)-\u0442\u0430\u0431\u043b\u0438\u0446\u044b. \u041d\u0430\u0447\u043d\u0435\u043c \u0441 TO=TS,{e}. \u0417\u0430\u0442\u0435\u043c \u043f\u043e \u0422\u041e \u043d\u0430\u0439\u0434\u0435\u043c \u04221=\u0422\u0410,{\u0435}, \u0434\u0430\u043b\u0435\u0435 T2=TS.{aa} \u0438 \u0422\u0417=\u0422\u0410,{\u0430\u0430}:
\n\u0422\u041e \u04222
\n\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u043e\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430
\n\u0432 S ?\u0435 — \u0430\u0430 S ?\u0432
\nab S ?abA {e} ab S ?\u0430\u042c\u0410 {\u0430\u0430}
\n\u04221 \u0422\u0417
\n\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u043e\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u043e\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430
\n\u042c \u0410?\u042c — \u0430\u0430 A?Saa {\u0430\u0430}
\n\u0430\u0430 A ?Saa {\u0430\u0430} ab A ?Saa {\u0430\u0430}
\nab A?Saa{aa} ba A?b
\n\u041f\u043e \u044d\u0442\u0438\u043c \u0442\u0430\u0431\u043b\u0438\u0446\u0430\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u043c \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0443\u044e \u0442\u0430\u0431\u043b\u0438\u0446\u0443:
\n\u0430\u0430 ab a ba bb \u042c \u0435 \u0422\u041e \u0430\u042c\u0422-1,2 \u0435,1 \u04221 \u04222\u0430\u0430,3 \u04222\u0430\u0430,3 \u042c,4 \u04222 \u0435,1 \u0430\u042c\u0422\u0417,2 \u0422\u0417 \u04222\u0430\u0430,3 \u04222\u0430\u0430,3 \u042c,4 \u0430 \u0432\u044b\u0431\u0440\u043e\u0441 \u0432\u044b\u0431\u0440\u043e\u0441 \u0432\u044b\u0431\u0440\u043e\u0441 \u042c \u0432\u044b\u0431\u0440\u043e\u0441 \u0432\u044b\u0431\u0440\u043e\u0441 \u0432\u044b\u0431\u0440\u043e\u0441 $ \u0434\u043e\u043f\u0443\u0441\u043a
\n\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u0439 \u043f\u043e \u0442\u0430\u0431\u043b\u0438\u0446\u0435 \u0440\u0430\u0437\u0431\u0435\u0440\u0435\u0442 \u0446\u0435\u043f\u043e\u0447\u043a\u0443 abaa \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:
\n(abaa,TO$,e) — (abaa,abT1$,2)
\n-(\u042c\u0430\u0430,\u042c\u04221$,2)
\n-(\u0430\u0430,\u04221$,2)
\n— (\u0430\u0430,\u04222\u0430\u0430$,23)
\n— (\u0430\u0430,\u0430\u0430$,231)
\n-(\u0430,\u0430$,231)
\n-(\u0435,$,231)
\n\u0422\u0420\u041c: \u0427\u0438\u0441\u043b\u043e \u0448\u0430\u0433\u043e\u0432, \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c\u044b\u0445 \u043a- \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u0441 \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0435\u0439 \u0442\u0430\u0431\u043b\u0438\u0446\u0435\u0439, \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u043e\u0439 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c no LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0435 G, \u043b\u0438\u043d\u0435\u0439\u043d\u043e \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u043f, \u0433\u0434\u0435 n — \u0434\u043b\u0438\u043d\u043d\u0430 \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u0446\u0435\u043f\u043e\u0447\u043a\u0438.
\n\u041f\u0440\u043e\u0432\u0435\u0440\u043a\u0430 LL(k)- \u0443\u0441\u043b\u043e\u0432\u0438\u044f.
\n\u041f\u043e \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044e \u043a \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0439 \u0434\u0430\u043d\u043d\u043e\u0439 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0435 G \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0440\u044f\u0434 \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u0432:
\n(1) \u042f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 G LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u043e\u0439 \u0434\u043b\u044f \u0434\u0430\u043d\u043d\u043e\u0433\u043e k ?
\n(2) \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043b\u0438 \u0442\u0430\u043a\u043e\u0435 k, \u0447\u0442\u043e G — LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430?
\n(3) \u0422\u0430\u043a \u043a\u0430\u043a \u0434\u043b\u044f LL(1) \u043b\u0435\u0432\u044b\u0435 \u0440\u0430\u0437\u0431\u043e\u0440\u044b \u0441\u0442\u0440\u043e\u044f\u0442\u0441\u044f \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e, \u0442\u043e \u0435\u0441\u043b\u0438 G \u043d\u0435 LL(1)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430, \u0442\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043b\u0438 \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u0430\u044f \u0435\u0439 LL(1)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 G’, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0439 L(G) = L(G’)?
\n\u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0432\u043e\u043f\u0440\u043e\u0441\u0430 \u0435\u0441\u0442\u044c \u043e\u0442\u0432\u0435\u0447\u0430\u044e\u0449\u0438\u0439 \u043d\u0430 \u043d\u0435\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u041c\u043e\u0436\u043d\u043e \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e \u0432\u0442\u043e\u0440\u0430\u044f \u0438 \u0442\u0440\u0435\u0442\u044c\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0438\u0447\u0435\u0441\u043a\u0438 \u043d\u0435 \u0440\u0430\u0437\u0440\u0435\u0448\u0438\u043c\u044b, \u043d\u043e \u044d\u0442\u043e \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u043e \u043d\u0435 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u0441\u044f. \u041f\u0440\u0438\u0432\u0435\u0434\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 LL(k)- \u0443\u0441\u043b\u043e\u0432\u0438\u044f:
\n\u0410\u041b\u0413 4: \u041f\u0440\u043e\u0432\u0435\u0440\u043a\u0430 LL(k)- \u0443\u0441\u043b\u043e\u0432\u0438\u044f.
\n\u0431\u0445\u043e\u0431; \u041a\u0421- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 G=(N,E,P,S) \u0438 \u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e k.
\n\u0412\u044b\u0445\u043e\u0434: \u00ab\u0414\u0430\u00bb — \u0435\u0441\u043b\u0438 G — LL(k)- \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 \u0438 \u00ab\u041d\u0435\u0442\u00bb \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435.
\n\u041c\u0435\u0442\u043e\u0434:
\n\u0421\u0443\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c\u0443: \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u0430, \u0438\u043c\u0435\u044e\u0449\u0435\u0433\u043e \u0434\u0432\u0430 \u0438\u043b\u0438 \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0440\u0430\u0441\u043a\u0440\u0443\u0442\u043a\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0435\u0440\u0435\u0441\u0435\u0447\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0432\u044b\u0445 k- \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0432\u0441\u0435\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0446\u0435\u043f\u043e\u0447\u0435\u043a \u0440\u0430\u0441\u043a\u0440\u0443\u0442\u043a\u0438. \u0415\u0441\u043b\u0438 \u044d\u0442\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043f\u0443\u0441\u0442\u043e, \u0442\u043e \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u044f\u0442 \u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c\u0443 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u0443, \u0438\u043d\u0430\u0447\u0435 \u0437\u0430\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u044e\u0442 \u0441\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u00ab\u041d\u0435\u0442\u00bb. \u0415\u0441\u043b\u0438 \u0432\u0441\u0435 \u043f\u0435\u0440\u0435\u0441\u0435\u0447\u0435\u043d\u0438\u044f \u043f\u0443\u0441\u0442\u044b — \u0437\u0430\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u044e\u0442 \u0441\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u00ab\u0414\u0430\u00bb. \u0414\u043b\u044f \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u043f\u0435\u0440\u0435\u0441\u0435\u0447\u0435\u043d\u0438\u044f \u0434\u0432\u0443\u0445 \u043f\u0440\u0430\u0432\u0438\u043b \u043c\u043e\u0436\u043d\u043e \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0437\u0430\u043f\u0438\u0441\u044c\u044e: (FIRSTk(b’) \u00a9kL)n(FIRSTk(c’) \u00aekL), \u0433\u0434\u0435 L=FIRSTk(a’) \u0438 \u0430’ — \u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u043f\u043e\u0441\u043b\u0435 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u0430.<\/p>\n","protected":false},"excerpt":{"rendered":"
\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 LL(k)-\u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a. \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e G=(N,E,P,S) — \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u0430\u044f \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0430 \u0438 w=a1,a2…an — \u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u0438\u0437 L(G). \u0422\u043e\u0433\u0434\u0430 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u0430\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043b\u0435\u0432\u043e\u0432\u044b\u0432\u043e\u0434\u0438\u043c\u044b\u0445 \u0446\u0435\u043f\u043e\u0447\u0435\u043a b0,b1..bm, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0439 S=b0,bi,pi ? bi+1 \u043f\u0440\u0438 0<=i<m \u0438 am=w. \u041f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c p0p1..pm-1 -\u043b\u0435\u0432\u044b\u0439 \u0440\u0430\u0437\u0431\u043e\u0440 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 w.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[],"_links":{"self":[{"href":"https:\/\/studentpmr.ru\/index.php?rest_route=\/wp\/v2\/posts\/1818"}],"collection":[{"href":"https:\/\/studentpmr.ru\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/studentpmr.ru\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/studentpmr.ru\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/studentpmr.ru\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1818"}],"version-history":[{"count":1,"href":"https:\/\/studentpmr.ru\/index.php?rest_route=\/wp\/v2\/posts\/1818\/revisions"}],"predecessor-version":[{"id":1819,"href":"https:\/\/studentpmr.ru\/index.php?rest_route=\/wp\/v2\/posts\/1818\/revisions\/1819"}],"wp:attachment":[{"href":"https:\/\/studentpmr.ru\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1818"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/studentpmr.ru\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1818"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/studentpmr.ru\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1818"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}