, , - . .
30- , .
, ( 1).
[i125]
1.
[i126] , VT[i127] ={a1, a2,...,an}, . α=(a1 a2,..., a|). VT[i128]. λ #. , λ (#) VT[i129]. V . .
- [i130] , , . .
( ) [i131] , Q = {q1, q2,..., qm}, . qi aj , . , , q0 qi. , , .[i132] qo () qk (), . D={, , }, [i133] , . {L, S, R}, L(ft) , R(ight) , a S(top) .
|
|
:
- : aj, ;
- : , qi[i134], aj, .. qj aj => qi am[i135] D;
- : , .. am, [i136] qi D.
- .[i137]
. [i138] , qi aj, .. (qi aj). , qk. .
, - iqi(0.)[i139] , ().
( ) [i140] :
1) a1, a2, , at , . , ;
2) qj;
3) k .
, :
a1 ak-1 ak+1 at a1 a2 ak-1 qj ak at
, , .
, . , , . , , , q1[i141], .