img162

162

11. Metody drzewowe

a pozostałe elementy są następujące:

Et = {1,0}, Z_N = {A,B,C,D,E,Z,W}, Z = {A}.

Wzorzec I można wygenerować następująco (cyfry w strzałkach oznaczają numery stosowanych produkcji):

,4-(i)— l(ZBZ) - (2)-> l(0BZ) — (2) —* 1{00{WCW)Z) - (5) --(5)- 1(00(1CW)Z) - (3) - 1(00(U(ZZ)W)Z) -(4)-»

- (4) - 1(00(11(OZ)W)Z) - (4) - 1(00(1 l(00)W)Z) - (5) —

-(5)- 1(00(11(00)1)^)-(4)- 1(00(11(00)1)0)

Podamy teraz reguły konstrukcji automatu %dft nad zbiorem etykiet wierzchołkowych Et = {aj,..., a„) rozpoczynającego wzorce generowane przez gramatykę ®t = (E,r, ty, Z):

%dft = (ę,h, ■ • ■ >ćm F),

gdzie:

(1)    Q := E — Et,

(2)    F := Z,

(3) dla każdej produkcji postaci A —* a(Ai... A_r(_aj) G ip o numerze i, funkcję przejścia S_a na A\,..., j4_r(„) definiujemy w następujący sposób:

S(A\,.Ar(a)) = (a, •) (dla A — a 6 P :    = {A, i))-

Skonstruujmy automat %dft rozpoznający rozważane wzorce:

(1)    <3= {A,B,C,D,E,Z,W},

(2) F = M),

(3)    S_l(Z,B,Z) = (A, 1), 6₀(W,C,W) = (B,2), 6_X(Z,Z) = (C, 3),

<o = (^,4),

ći = (VP,5),

«i(W,£», W) = (A, 6), Ć₀(W,£,W) = (D,7),

«»WW0 = (£,8).

Rozpoznawanie wzorca 1 przebiega następująco (patrz Dodatek 4): (rp(1(00(11(00)1)0)), A) I—

111

(6,(rp(0), rp(0(l 1(00)1),rp(0)), A) ł—

(«i («o, «o(rp(l), ^rp( 1(00)), rp(l)), Ć₀), A) I—

(^i(6₀,6o(6i,ói(rp(0),rp(0)),<5i),Ćo), A) I—