. , A = {a1, a2,... am}, Q = {q1, q2,... qn} R = {qiaj q'ia'jdk}, dk - , dk {L, R, E}. q0. , qy qn, . , P, ~ P, , , , P(l) , P - , l - ( : l = |z|). , , .
(). () , . ? , , , : ? , .
, . , . , . , , . ( ), ( ). .
. , , , , , . .
, , . , ( ). , . , - . , , .
|
|
, , Z, z Z. , , qy. , , qn ( ).
, , , (.. ), qy. , : qn, .
, , qn.
? , . , . . .
. , (Z NP), , , P(l), l = |z|.
: . P.
NP? . -, (P NP. ). -, NP (-). . - X ( , , ). P(l) , , -. , - NP.
, , ( , L?). , , L, . , , 8 , . , , : , ? .
, P NP. NP , NP -, , . , , P = NP. , .
, . Z NP, , , .. (~Z) NP. , : , , . . , 1000 ? , . : , 1000 ?. . , , . , , , NP - , .
|
|