img156

156

11. Metody drzewowe

drzewowe widoczne obok wspomnianych scen. Zapisując te trzy drzewa--reprezentacje w postaci nawiasowej (patrz rozdział 9), otrzymamy:

I    scena - b(vd ta),

II    scena - b(vd ta(vd)),

III    scena - b(vd td(vd ud)).

a)    b)

Rys. 11.1. Składowe pierwotne opisu drzewowego oraz trzy sceny opisane strukturalnie jako drzewa (opis w tekście)

Zdefiniujmy teraz gramatykę ®edt generującą rozważane sceny, na bazie której będziemy mogli skonstruować automat rozpoznający te sceny. Gramatyka ta jest piątką (patrz Dodatek 4):

©bdt = (E,r, r,ęp,Z),

gdzie zbiór produkcji ip przedstawiony na rysunku 11.2 jest określony w następujący sposób:

(2) D - d,

(1) A —► b(vDtB),