img200

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

Konfiguracją początkową jest (77, A), gdzie 77 jest zapisem drzewa w postaci nawiasowej, A - słowem pustym, a konfiguracją końcową jest (A, r), gdzie r jest ciągiem numerów produkcji gramatyki drzewowej prowadzącym do wygenerowania drzewa 77, A 6 F (zbiór stanów końcowych). Zatem zbiór drzew akceptowalnych przez automat drzewowy %dft (^w obu przypadkach) określimy jako:

T(%dft) = {'71 (>?, A)l— * -(A, r)}.

Wprowadzimy teraz definicję grafu klasy EDG używanego do reprezentacji obrazów strukturalnych [33].

Skierowanym, wierzchołkowo i krawędziowo etykietowanym grafem (grafem EDG - ang. Edge-labelled Directed Graph) nazywamy piątkę

H = (V,E, s,r,ó),

gdzie V - skończony, niepusty zbiór wierzchołków, £ - skończony, niepusty zbiór etykiet wierzchołkowych, T - skończony, niepusty zbiór etykiet krawędziowych, E - zbiór krawędzi o postaci (u, A, tu), gdzie v, w 6 V, A g T, <j> : V —* £ - funkcja etykietowania wierzchołków.

Definicje dotyczące grafów klasy Cl i rodziny ekspansywnych gramatyk grafowych zostały sformułowane na podstawie pracy [35].

Niech H = (V, E, £, r,<j>) będzie grafem EDG o m wierzchołkach, którym przypisano indeksy 1,.... m. Etykietowaną macierzą przyległości dla H nazywamy macierz A = [ay]_mxm taką, że

a)    ctjj = 0, jeśli (u,,/?, v_;) 6 E, gdzie t),(tty) jest wierzchołkiem o indeksie t(j),

b)    a,j = 0, w przeciwnym przypadku.

Funkcją maksymalnego poprzednika nazywamy funkcję

maxind : {ł,...,m}—»{!,... ,m} taką, że maxind(k) = l, gdy

1) z wierzchołka o indeksie l - v/ wychodzi krawędź wchodząca do wierzchołka o indeksie k - u*,