img198

198

D4. Wybrane pojęcia teorii języków drzewowych i grafowych

gdzie j4,i4i,j4_2ł...,j4_r(a) € E#, a G Et, ri,r₂,...,r_r(_a) € I\ natomiast a(ri>lir2i42.. .7V(_a)i4_r(_a)) jest drzewem    (zapisanym w postaci na

wiasowej) o korzeniu a i r(a) następnikach-liściach A\, ^2,..., ^4_r(a) P°-łączonych z korzeniem r(a) krawędziami zaetykietowanymi t\ , r₂,..., r_r(₀) (odpowiednio) i skierowanymi od korzenia do liści.

Automatem %dft ² wyjściem nad zbiorem etykiet wierzchołkowych Er = {ai,..., a_n} rozpoznającym drzewa T nazywamy (n + 2)-krotkę:

&EDT = (Qth$'"t6ntF)t

gdzie Q - skończony zbiór stanów, 6t, k =    - funkcja przejścia

zdefiniowana następująco:

6_t : Q^r(ak) -> Q x N,

gdzie at € Et, N - zbiór liczb naturalnych, F CQ - zbiór stanów końcowych.

Zdefiniujmy teraz funkcję rp (patrz Dodatek 3) dla automatu 21 dft'

1)    Dla wierzchołka a € Sr będącego liściem (tzn. nie posiadającego następników - r(a) = 0):

rp(a) = (A, i) »«, = (A, i),

gdzie i jest numerem produkcji, na bazie której została zdefiniowana 6_a, wypisywanym na wyjście.

2)    Dla wierzchołka a € Er posiadającego r(a) następników, które są korzeniami poddrzew y\,..., y_r(a)

rp(a(y\ ...y_r(_a))) = (A,i) O

3A\, • . . , -^r(a) £ Q ' ^o(-^.l > • • • , ^J4r(«)) ⁼ {A, i)

oraz rp(yjfc) = (Ak,j{k)), k = l,...r(a), gdzie i jest numerem produkcji, na bazie której została zdefiniowana 6_a(A\_ij4_r(₀)), natomiast j(k) jest numerem pierwszej produkcji generującej drzewo y_; (numery produkcji są wypisywane na wyjście), czyli

rp(a(Vi • • -yr(a))) = ^a(rp(j/i),..., rp(y_r(a))).