img199

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

Automatem %DFEDT z wyjściem nad zbiorem etykiet wierzchołkowych Et — {m,... , a„} i zbiorem etykiet krawędziowych T rozpoznającym drzewa EDT nazywamy (n + 2)-krotkę:

&DFEDT = (Q,bi,-- -ib„,F),

gdzie Q i F - jak w poprzedniej definicji, St, k =    jest funkcją

przejścia zdefiniowaną następująco:

6_k : (rQ)^r<°P - Q x N,

gdzie a* G Et, N - zbiór liczb naturalnych, = {rA \ r € T, A G Q}.

Funkcję rp dla automatu 21 dfedt zdefiniujemy analogicznie jak dla automatu 21 dft

1)    dla wierzchołka a G Sr będącego liściem

rp(a) = {A, i) 6_a = (-4, «')>

gdzie «' - numer produkcji, na bazie której została zdefiniowana ó„, wypisywany na wyjście,

2)    dla wierzchołka a G Et posiadającego r(a) następników połączonych z wierzchołkiem a krawędziami rj,..., r_r(_a) i będących korzeniami poddrzew j/i,..., y_r(_a)

^rP(^a(^TlVl • • • ^r(a)J/r(a))) = (A, «') O

3A\,..., A_r(_a) G Q : śo(r*i A\,... Zr(a)^4r(a)) — (;4, i)

oraz rp(y_k) = (i4*,j(jb)), k = l,...,r(a) gdzie i,j(k) są takie jak w analogicznej definicji, czyli

rp(a(nyi ■ • -T-rtajyrfo))) = MmKvi).. • •,T_r(a)rp(y_r(o))).

Konfiguracją automatu drzewowego z wyjściem (w obu przypadkach) nazywamy parę (INPUT,OUTPUT), gdzie INPUT - ciąg symboli opisujący analizę drzewa zapisanego w postaci nawiasowej, OUTPUT - ciąg numerów produkcji, jakie zostały użyte podczas dotychczasowej analizy drzewa.