img158

158

11. Metody drzewowe

Rys. 11.3. Generacja sceny zgodnie z zasadami gramatyki drzewowej

(2)    F := Z,

(3)    dla każdej produkcji postaci A —*■ a(r\A\... T_r(_ay4_r(_a)) € V o numerze i, funkcję przejścia 6_a na t\A\,..., T_r(_a)A_r(a) definiujemy w następujący sposób:

6a(n^i, - .,^r(a)^r(a)) = (A,i) (dla A —■ a €    : ba = (j4,i)).

W naszym przypadku mamy:

(1) Q=M, £,£>},

(2 )F={A},

(2) 6„(vD,tB) = (A,l),    6_d = (D, 2), «_a = (B,3),

= (B,4),    «,,(»£>, u£>) = (B,5).

Prześledźmy rozpoznawanie wskazanej sceny (z rys 11.1 c), obserwując przejścia pomiędzy konfiguracjami automatu ^dfedt (patrz Dodatek 4).

(rp(b(vd ta(vd)))_f A) I-(6_b(v rp(d), t rp(a(vd)))_} A) I-

ł— (f>b(v6d, tf>_a{rp(vd))), A) I-(6_b(v6d, t6_a(v rp(d))), A)h—

I-(^(v^d, *M^d))>^A)¹-(M^v*d, t6_a(vD)), 2) I-

I-(^(t^, <£), 24) I-(6_b(vD,łB), 242) I-(A, 2421).

Jak widać, scena została zaakceptowana (A G F) i rozpoznana prawidłowo (ciąg produkcji: 1242 - czytany od prawej do lewej).